Problem: http://www.spoj.com/problems/BUD13TLF/
The problem is with my DP state: I have recursion for this as: let k=space left,visited[ ] array to keep track of visited elements , array a[ ] represent w1,w2,..wn. and function int solve (k , visited[ ]) is my function that returns ans this is my function:
int solve(int k,vector vis){
if(k<0)return 0;
if(k==0)return 1;
int ans=1;
loop(i,n){
if(!vis[i]){
vis[i]=1;
ans+=solve(k-a[i],vis)%MOD;
vis[i]=0;int j;
for(j=i+1;a[j]==a[i];j++);
j--;
i=j;
}
}
if(ans!=1) ans--;
return ans;
}
the problem is How Do I define my DP state because visited(vector/array) can be huge (max 2^100 possibilities if i choose bitmasks or bitsets)? also please comment on how can I represent a DP state if my DP state depends on whole array ?