@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.
