in Algorithms edited by
37 votes

The subset-sum problem is defined as follows. Given a set of $n$ positive integers, $S = \{ a_1, a_2, a_3, \dots , a_n \}$, and positive integer $W$, is there a subset of $S$ whose elements sum to $W$? A dynamic program for solving this problem uses a $\text{2-dimensional}$ Boolean array, $X$, with $n$ rows and $W+1$ columns. $X[i, j], 1 \leq i \leq n, 0 \leq j \leq W$, is TRUE, if and only if there is a subset of $\{a_1, a_2, \dots, a_i\}$ whose elements sum to $j$.

Which of the following is valid for $2 \leq i \leq n$, and $a_i \leq j \leq W$?

  1. $X[i, j] = X[i-1, j] \vee X[i, j-a_i]$
  2. $X[i, j] = X[i-1, j] \vee X[i-1, j-a_i]$
  3. $X[i, j] = X[i-1, j] \wedge X[i, j-a_i]$
  4. $X[i, j] = X[i-1, j] \wedge X[i-1, j-a_i]$
in Algorithms edited by


second part analysis anyone?
Its simple. When you draw 2 D array then on row side you have n values and on column side you have 0 to W values = W+1 values. Now array[n][W] wil give the truth value.

Subscribe to GO Classes for GATE CSE 2022

3 Answers

24 votes
Best answer

This is analogous to the dynamic programming solution to $0/1$ knapsack problem.

Consider the capacity of the knapsack, i.e., $W$ to be analogous to $J$(the total sum here).

The solution exploits the optimal substructure of the problem.

At each stage we can have $2$ options:

Case $(1)$: Either we take an item(in this question either we consider the element $A_i$)  along with the total solution to previous sub-problem(total solution here means the total sum obtained  till previous sub-problem)

in which case we choose $A[i-1]$$\left [ j-a_{i} \right ]$

$A[i-1]$ indicates we are considering solution to previous subproblem and

$A[j-a_i]$ means we have considered element $a_i$ and now remaining sum is $J-a_i$ which has to be further considered.

Case $(2)$: Or we do not consider the item(in this case the element $a_{i}$) in which case we only consider the solution to previous subproblem, which is, $A[i-1][J]$

Since the whole solution to this subset-sum problem is Logical OR(+) of cases 1 and 2, we eliminate options $C$ and $D$ because both are considering the Logical AND of the two parts of the solution.

Now, since here in the given question we are given a boolean array $X[n][W+1]$

So, an entry $X[i][j]$ is true only if sum $j$ is possible with array elements from $0$ to $i$.

So, for Each element of array, $a_{i}$, we consider two possibilities:

(1) Either we can ignore it and still get our possible sum, which is, $X[i-1][j]$


(2) We could include element $a_i$ and then get our required sum, which is, $X[i-1][j-a_i]$

And finally, to get $X[i][j]$, we take logical or of the above two cases.

Hence, answer is option B.

Reference : 

By using the analogy of the problem and solution between subset-sum problem and $0/1$ knapsack problem, the above video clearly explains the how the solution to the problem is structured .

edited by


Here condition given is 2 ≤i ≤ n, and ai ≤ j ≤W. If for X[i,j] ,  j is greater than ai then X[i-1,j] will always be blank. so whats the use of the condition x[i-1,j]?
edited by

@Ayush Upadhyaya

Nice solution. It is an application of 0/1 Knapsack while I thought it is LCS by seeing the Ans options. Thanks for ans :)

But from problem given, how do u come to know, it will be 0/1 Knapsack and it will not be only a subset sum problem?


@srestha-Thank you. It is an application of subset sum problem only but you see the recurrence is somewhat similar to the recurrence of 0/1 knapsack where we either take the item or don't take the item.


@Ayush Upadhyaya @Arjun Please explain the the part where 2<=i<=n. Does it will not effect the solution.

if the weight of item i i.e ai is greater than j then we can not element into the subset in that case second case occur but if the weight of item i i.e ai is less than or equal to j then we include the item i and remaining weight we try to fill up with the lower indexed elements.
12 votes

I think answers are


$X[i][j] = X[i-1][j] \cup X[i-1][j-a_i]$

$\text{ We calculate the value of } X[i][j] \text{ as if we include the value }$

$ a_i \text{ in the subset } X[i-1][j-a_i] \text{ or we do not include the value in the subset} X[i-1][j].$


// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
    //  with sum equal to i
    bool subset[sum+1][n+1];
    // If sum is 0, then answer is true
    for (int i = 0; i <= n; i++)
      subset[0][i] = true;
    // If sum is not 0 and set is empty, then answer is false
    for (int i = 1; i <= sum; i++)
      subset[i][0] = false;
     // Fill the subset table in botton up manner
     for (int i = 1; i <= sum; i++)
       for (int j = 1; j <= n; j++)
         subset[i][j] = subset[i][j-1];
         if (i >= set[j-1])
           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
    /* // uncomment this code to print table
     for (int i = 0; i <= sum; i++)
       for (int j = 0; j <= n; j++)
          printf ("%4d", subset[i][j]);
     } */
     return subset[sum][n];
edited by
2 votes

Similar to $0|1$ knapsack

if $W(n)>m\rightarrow01KS(m,n-1)$



We are not sure whether this object will give maximum profit or not. So one time we are taking it and calculating rest.


One time we are not taking that element and calculating rest.




Related questions