targetSum.c

/*
    Name: targetsum.c
    Copyright:
    Author: Mr.Kindle
    Date: 21-12-22 21:04
    Description: This code print total number of ways the target sum can be found using the given 'n' coins of
    different denimination.
    e.g : One can make a sum of 15 using coins of 2,3,5 in 7 ways.
    All the matrix (2 1-D matrix and 1 2-D matrix) are dynamically allocated.

    replit: https://replit.com/@PrajjwalTripat2/TargetSum#main.c
*/



#include <malloc.h>
#include <stdio.h>
#define MAX 30



int main(void) {
  int n, t_sum;

  int i, j,col;
  int *coin, *target;
  int * dpmat;

  printf("Enter total number of coins of different denomination\n");
  scanf("%d", &n);
  coin = calloc(n, sizeof(int));
  printf("\nPlease enter all different denomination of coins : ");
  for (i = 0; i < n; i++) {
    printf("\nEnter coin %d:  ", i + 1);
    scanf("%d", &coin[i]);
  }
  printf("\nEnter target sum:  ");
  scanf("%d", &t_sum);
  target = calloc(t_sum + 1, sizeof(int));
  for (i = 0; i <= t_sum; i++)
    target[i] = i;

dpmat = calloc(n * (t_sum + 1), sizeof(int));
col = t_sum + 1;


  for (i = 0; i < n; i++) {
    for (j = 0; j <= t_sum; j++) {
/*for first row of dpmatrix*/
      if (i == 0) {
        if (target[j] % coin[i] == 0)//
          dpmat[i * col + j] = 1;
      } else if (coin[i] > target[j])//if value of coin greater than the target at column j
        dpmat[i * col +j] = dpmat[(i-1) * col + j];
      else {
          /*using the technic exclude, upper value and include*/
        dpmat[i * col + j] = dpmat[(i-1) * col + j] + dpmat[i * col + (target[j] - coin[i])];
      }
    }
  }
printf("\n\nFollowing is your dpmatrix: \n\n");
  for (i = 0; i < n; i++) {
    for (j = 0; j <= t_sum; j++) {
      printf("%2d ", dpmat[i * col +j]);
    }
    printf("\n");
  }
  /*The last element of the dpmatrix is the answer hence printing the last element*/
  /*Last element is the cross section of the last row and the last column*/
  printf("\nTotal number of ways = %d",dpmat[(n - 1)* col + (t_sum)]);
 free(coin);
  free(target);
  free(dpmat);
  return 0;
}