The Gateway to Computer Science Excellence
+31 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 by
edited by | 3.4k views
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.

3 Answers

+19 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]?

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

+11 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
0 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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,470 answers
95,272 users