@atul.. The table is used to record the state of subsets not print them.. (I am assuming that's what u meant)..Hence keeping that in mind, yes it captures all subsets... Now once A[N, K] is 1 that means there are some subsets whose sum will be equal to K. Hence, to find all such subsets we will backtrack accordingly...
-------------------------------------------------------------- A[i,j] -> Whether using first 'i' items a sum of 'j' can be made.. A value of 0/1 indicates whether its possible or not... Now there are 2 ways we can make a subset having sum j.. 1) Consider that W[i] is part of the subset, then A[ i - 1, j - W[i] ] should be 1. // Hence while generating the subsets if A[i -1, j - W[i] ] = A[i, j] =1 , then W[i] will be part of subset... Point to be noted - the part of "that subset" which will be generated using the path whose intermediate nodes are (A[i, j] , A[i-1, j - W[i]]) 2) Say 'i'th element doesn't contribute to the subset. Hence for A[i, j] to be 1, A[i-1, j] should be 1. // Hence when A[i-1, j] = A[i, j] = 1, then W[i] won't be a part of the subset... Point to be noted - the part of "that subset" which will be generated using the path whose intermediate nodes are (A[i, j] , A[i-1, j]) ----------------------------------------------------- On Jan 7, 11:37 pm, atul anand <atul.87fri...@gmail.com> wrote: > @Lucifer : > > for W[]={1,3,2,1,2} and Wmax=4. > this array will be formed. > > 0 > > 1 > > 2 > > 3 > > 4 > > 0 > > 1 > > 0 > > 0 > > 0 > > 0 > > 1 > > 1 > > 1 > > 0 > > 0 > > 0 > > 3 > > 1 > > 1 > > 0 > > 1 > > 1 > > 2 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 1 > > 2 > > 1 > > 1 > > 1 > > 1 > > 1 > > is it printing all subset ?? if yes then may be i am not getting it.. > > btw one query :- > > b) if A[N -1 , K] = 1, > b1) then *W[N] doesn't belong to the subset* , continue > recursively ( goto step a). > > why??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.