Блог пользователя Medeali

Автор Medeali, история, 10 месяцев назад, По-английски

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 .

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how can we help if we dont know the task?? paste the link to the task :)

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
10 месяцев назад, # |
Rev. 3   Проголосовать: нравится +38 Проголосовать: не нравится

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

??
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

but i have included b++ in my code if k==0 which means that after the function finishes i add emety subset if k==0

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please help i have been teying but still failing