CareerCup

'solution' and 'denom'are Global variables or you can also pass them( solution needs to be passed by reference)

vector< vector<int> > solution;
vector<int> denom;

from main call as:
vector<int>sub;
subsum(6,sub,0);
and then

if( numelments(solution) == 0 ) "NOT POssible"
else "nO of WAys = " NUmEL(solution);

subsum(N,vector<int> subsol,el)
{
 subsol.push(el);
 N=N-el;
 if( N==0 )
      if( !find( subsol in solution ) ) solution.push(subsolution);
 
 for( every element E in denom ) 
	if( E <= N ) subsum(N,subsol,E);

 return;
}

find() method can be easily constructed i think

it can be solved in O(nk), where size of array is n and k is the desired sum.

use DP as used in sum of subset.

it can be solved in O(nk), where size of array is n and k is the desired sum.

use DP as used in sum of subset.

answer is not 6 it is 5

int main()
{
int s[]={1,2,5,10};
int n=6,m=4;
int r=count(n,s,m);
printf("%d",r);
return 0;
}
int count(int n,int *s,int m)
{
if ( n == 0 )
return 1;
if ( n < 0 )
return 0;
if ( m <= 0 && n >= 1 )
return 0;

return count( n,s, m - 1 ) + count( n - s[m-1],s, m );

}

pls check d above code
nd correct if wrng

@aditya
i hve tried it on few tast cases and its wrkng fine..

its a simple dp question
first sort all the coins
int func(int n,int index=0){
if(n<0)
return 0;
if(!n) return 1;
if(dp[n][index]!=-1) return dp[n][index];
return dp[n][index]=func(n-arr[index],index)+func(n,index+1);
}

Sorry a small missing of termination condition
first sort all the coins
vector<int> arr;
int func(int n,int index=0){
if(n<0)
return 0;
if(!n) return 1;
if(index==sz(arr)) return 0;
if(dp[n][index]!=-1) return dp[n][index];
return dp[n][index]=func(n-arr[index],index)+func(n,index+1);
}

int func(int[] d, int ind, int N) {
    if(N == 0)
        return 1;
    if(N < 0)
        return 0;
    int ways = 0;
    for(int i = 0; d[ind]*i < n; i++) {
        ways += func(d, ind+1, N-d[ind]*i);
    }
    return ways;
}

int coins[4] = { 1,2,5,10};
int noOfDenominations = 4;
void denominations(string s,int remSum, int lastUsedCoinIndex)
{
	if(remSum == 0 )
	{
		cout << s << endl;
		return;
	}else{
		for(int i = lastUsedCoinIndex ; i < noOfDenominations ; i++)
		{
			if(remSum >= coins[i])
			{
				char temp[10];
				itoa(coins[i],temp,10);
				denominations(s+temp,remSum-coins[i],i);
			}
		}
	}

}

NA