Title Subset Sum Problem Find all subsets S1 S2 S3 Sn for a

Title: Subset Sum Problem Find all subsets S1, S2, S3, ...., Sn for a given set S = { e1, e2,......, en} of n positive integers whose sum is equal to a positive integer D. For an example, S={2, 6, 8, 5, 1, 10} and D = 9, there are two subsets (solutions): S1={2, 6, 1} and S2={8, 1}.   In our search tree, every path from root node to i^thlevel represents a subset of S. If sum of the element values that are included in a path is equal to D, then we have a solution to the problem. If the subset sum becomes greater than D, then we should not further explore that path (pruning!!). Any Java code to accomplish this would be appreciated!

Solution

int n, d, w[10], x[10], count=0; void subset(int cs, int k, int r) { int i; x[k] = 1; if(cs + w[k] == d) //if the first element is equivalent to the sum that is required { std::cout<< \"\ \ Solution \" << ++count << \" is:\"; for(i=0; i<=k; i++) // so if the subset criteria are met then the array is printed. if(x[i] == 1) std::cout << w[i] << \" \"; } else if(cs + w[k] + w[k+1] <= d) subset(cs + w[k], k+1, r - w[k]); //check if subset criteria are met if(cs + w[k+1] <= d && cs + r - w[k] >= d) //else backtrack { x[k] = 0; subset(cs, k+1, r-w[k]); } } int main() { int sum=0, i; std::cout << \"enter n\ \"; std::cin >> n; std::cout < <\"enter \" << n << \" elements\ \"; for(i=0; i> w[i]; for(i=0; i> d; if(sum < d) std::cout<<\"INVALID SOLUTION\ \"; else subset(0,0,sum); }