The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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 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]$
asked in Algorithms by Veteran (68.8k points)
edited by | 1.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.

Hope it will help to understand the problem 

2 Answers

+2 votes
Best answer

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

Consider the Capacity of the knapsack W 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 Ai)  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][j-ai]

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

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

Case (2) Or we do not consider the item(in this case the element ai) 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 part of 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, ai, we consider two possibilites

(1) EIther we can ignore it and still get our possible sum

Which is X[i-1][j]


(2) We could include element ai and then get our required sum.

Which is X[i-1][j-ai]

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 .


answered by Boss (5.2k points)
edited by

This might help along with the solution ...

+7 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];


answered by Loyal (4.1k points)
edited by

Ans. B

Thumbs up for posting video here.

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

32,330 questions
39,146 answers
36,501 users