// C program for coin change problem.
#include<stdio.h>
int count( int S[], int m, int n )
{
int i, j, x, y;
// We need n+1 rows as the table is constructed
// in bottom up manner using the base case 0
// value case (n = 0)
int table[n+1][m];
//**QUESTION: Why initializing table[0][i] = 1 below in loop because if sum is 0 why we need 1 coin?**
// Fill the enteries for 0 value case (n = 0)
for (i=0; i<m; i++){
table[0][i] = 1;
}
}
Check the geeksforgeeks article code in brute force section.
// If n is 0 then there is 1 solution
// (do not include any coin)
if (n == 0)
return 1;
how donot including any coin is 1 solution ?? suppose coin set ={1,2,3} if 3 coins then we should initialize it with 3 because we donot include 1st coin,we donot include 2nd coin , then we donot include 3rd coin ??
(do not include any coin) = Empty set.
The question can be rephrased as “Find the number of different sets such that sum = n and contains elements only from S”. Two sets are different if their sizes are different else there should be one element that differs in the sets.