Medeali's blog

By Medeali, history, 16 months ago, In English

my code :

include

using namespace std; int subsum(int A[],int n,int index,int sum,int x){ if(sum==x && index!=0) return 1; if(index==n) return 0; return subsum(A,n,index+1,sum+A[index],x)+subsum(A,n,index+1,sum,x);

} int main() { int n,x; cin>>n>>x; int A[n]; for(int i=0;i<n;i++) cin>>A[i]; int b=subsum(A,n,0,0,x); if(x==0) b++; cout<<b; return 0; } Given an array A of N elements and an integer K , we want you to calculate the number of subsets of A whose sum of elements is equal to K .

B is a subset of A if B can be obtained by removing zero or more elements from A .

  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
Rev. 3   Vote: I like it +38 Vote: I do not like it

This is a classic problem. It can either be tackled using recursion or bit-masking (Complete search) as bits being (0, 1) represent the states of taking the subset or not. Further optimization (for large values of n) would be using Dynamic programming or meet in the middle for the bit-masking.

However, Modified version of your code accepted. I changed the base case. The issue was the fact that empty set was considered as an invalid subset on calculating number of subsets whose elements summation is equal to k and given the problem constraints; |k| < 1000, k can equal zero and hence the empty set should be a valid option.

In short, change base case to

??