Interview Questions

Subset sum problem

The subset sum problem is an important problem in computer science. Below we'll provide two common algorithms for solving this problem. The challenge is to determine if there is some subset of numbers in an array that can sum up to some number S. These algorithms can both be implemented to solve Array Addition I and Array Addition.
## Naive solution

The algorithm for the exponential time, naive solution, is as follows: First we will generate every possible set (the power set), and then check if the sum of any of these sets equals the sum S. For example:
arr = [1, 2, 3]
sum = 5
All possible sets:
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]
We can see that we can get a sum of 5 by adding the elements in the set [2, 3]. To generate all possible sets of an array, we'll implement the following algorithm:
(1) The initial power set only contains the empty set: [[]]
(2) Then we loop through each element in the array and add it to every element in the power set. Then we take the union of these two sets.
(3) Once we get the power set, we check to see if the sum equals our goal S.
## Example

arr = [1, 2, 3]
sum = 5
sets = [[]]
Step 1: Add 1 to the power set
[[], [1]]
Step 2: Add 2 to the power set
[[], [1], [1, 2], [2]]
Step 3: Add 3 to the power set
[[], [1], [1, 2], [2], [1, 3], [2, 3], [1, 2, 3], [3]]
## Code

^{n}) time because in the worse case, we need to create every possible subset of the array to check if any of them equal the goal sum, and there are 2^{n} possible sets.
## More efficient solution: Dynamic Programming

This algorithm runs in O(*Sn*) time where S is the sum. You can read more about the running time here.
## Sources

http://www.careercup.com/question?id=12899672
http://www.careercup.com/question?id=5761544004567040
http://www.skorks.com/2011/02/algorithms-a-dropbox-challenge-and-dynamic-programming/
http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/

function ArrayAdditionI(arr) { // get largest number and remove it from array var sum = Math.max.apply(null, arr); arr.splice(arr.indexOf(sum), 1); // power set var sets = [[]]; // generate the power set and for each new set // check if the temporary sum equals our sum above for (var i = 0; i < arr.length; i++) { for (var j = 0, len = sets.length; j < len; j++) { var temp = sets[j].concat(arr[i]); sets.push(temp); var s = temp.reduce(function(p, c) { return p + c; }); if (s === sum) { return "true"; } } } return "false"; } ArrayAdditionI(readline());

def ArrayAdditionI(arr): # get largest number and remove it from array goal = max(arr) arr.remove(goal) # power set sets = [[]] # generate the power set and for each new set # check if the temporary sum equals our sum above for i in range(0, len(arr)): sets_len = len(sets) for j in range(0, sets_len): temp = sets[j] + [arr[i]] sets.append(temp) if sum(temp) == goal: return "true" return "false" print ArrayAdditionI(raw_input())This algorithm runs in O(2

function ArrayAddition(arr) { // get largest number and remove it from array var sum = Math.max.apply(null, arr); arr.splice(arr.indexOf(sum), 1); // clever way to get rid of negative values for (var i = 0; i < arr.length; i++) { if (arr[i] < 0) { sum -= arr[i]; arr[i] = 0; } } // table to track elements var table = [[]]; // fill first row for (var i = 1; i <= sum; i++) table[0][i] = false; // fill first column for (var i = 0; i <= arr.length; i++) { table[i][0] = true; if (i !== arr.length) table.push([]); } // dynamic programming solution for (var i = 1; i <= arr.length; i++) { for (var j = 1; j <= sum; j++) { table[i][j] = table[i-1][j]; if (table[i][j] === false && j >= arr[i-1]) { table[i][j] = table[i][j] || table[i-1][j-arr[i-1]]; } } } return table[arr.length][sum]; } ArrayAddition([1, 2, 6, 4, 7, 12]);

def ArrayAddition(arr): # get largest number and remove it from array goal = max(arr) arr.remove(goal) # clever way to get rid of negative values for i in xrange(0, len(arr)): if arr[i] < 0: goal -= arr[i] arr[i] = 0 # table to track elements table = [[False]*(goal+1) for r in xrange(0, len(arr)+1)] # fill first column for i in xrange(0, len(arr)+1): table[i][0] = True # dynamic programming solution for i in xrange(1, len(arr)+1): for j in xrange(1, goal+1): table[i][j] = table[i-1][j] if table[i][j] == False and j >= arr[i-1]: table[i][j] = table[i][j] or table[i-1][j-arr[i-1]] if table[len(arr)][goal]: return "true" else: return "false" print ArrayAddition([1, 2, 6, 4, 7, 12])

mrdaniel
published this on 2/5/16 **|**

19

dude, the video is not clear. I normally love your stuff but this one is an anomaly.

ithoughtso

commented on 04/17/16

17

@mrdaniel, as @SJern, @codesmith and @artykreaper noticed, the dinamic programming solution given above is not always correct if the input array contains negative numbers.
For this simple case:
[-1,1,2,3] returns 'false' but 1 + 2 = 3
I think the problem is that in the first for loop, labeled "#clever way to get rid of negative numbers" you are implicitly using all the negative values to obtain the total sum.
A modification can be perfomed to address this issue. The complexity rises to O(Sn) with S the sum of the absolute values of the input array.
A larger memoization matrix, with broader range (negative and positive) allows to calculate the current values from the preview ones when there are negative values in the input.
This is what I came out with:

```
def ArrayAddition(arr):
sum_positive = sum([x for x in arr if x > 0])
sum_negative = sum([x for x in arr if x < 0])
num_columns = -sum_negative + 1 + sum_positive
# get largest number and remove it from array
goal = max(arr)
arr.remove(goal)
'''
# clever way to get rid of negative values
for i in xrange(0, len(arr)):
if arr[i] < 0:
goal -= arr[i]
arr[i] = 0
'''
# table to track elements
table = [[False]*num_columns for r in xrange(0, len(arr)+1)]
'''
# fill first column
for i in xrange(0, len(arr)+1):
table[i][0] = True
'''
table[0][-sum_negative] = True
# dynamic programming solution
for i in xrange(1, len(arr)+1):
for j in xrange(num_columns):
table[i][j] = table[i-1][j]
if table[i][j] == False and 0 <= j - arr[i-1] and j-arr[i-1] < num_columns:
table[i][j] = table[i][j] or table[i-1][j-arr[i-1]]
if table[len(arr)][-sum_negative + goal]:
return "true"
else:
return "false"
print ArrayAddition([-1,1,2,3])
```

I am not sure if this can be further optimized.
Corinto

commented on 08/18/16

7

```
for (var i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
sum -= arr[i];
arr[i] = 0;
}
}
```

I think the getting rid of negative values code above wouldn't work, if any of the negative numbers did not belong to any subset of numbers in the array that can sum up to S. For example, [3,4,-1,8,12] wouldn't work I think. Am I mistaken?
SJern

commented on 04/05/16

3

@SJern I believe you are correct. With the example code provide above, if you change 7 to -7 the result changes from true to false, even though you can still add 2,4, and 6 to get 12 regardless of whether 7 is positive or negative.

codesmith

commented on 04/05/16

2

Is this a legitimate question to expect for a coding bootcamp interview? Asking because it's on coderbyte's preparatory coursework for Makersquare.

junkrabbit

commented on 08/04/16

1

@mrdaniel could you provide clarification on how to handle negative numbers? as said below, subtracting the negative numbers from the max doesn't work.

artykreaper

commented on 07/17/16

1

Regarding the nested for loop in the first solution. Why do we need to declare len? the code does not run properly without it
for (var j = 0, len = sets.length; j < len; j++)
Why does that work? wouldn't this be simpler?
for (var j = 0; j < sets.length; j++)

Cohno

commented on 07/28/16

1

@Cohno, the reason we explicity set the length of sets equal to len is because we want to loop through all of the "sets" array before we start adding elements to it, which would make the length of "sets" larger.

mrdaniel

commented on 07/28/16

1

I agree with the other comments. This doesn't work for the first negative values I tried. Cool solution but it should probably be updated.

noHands

commented on 11/30/16

1

Video is super confusing. Also negative numbers workaround does not work!

iandanforth

commented on 04/12/17

0

3:10 - "The true means you keep going up the column until you hit a false" - huh? Not an explanation.
"Now you go left, now you go up" - What the heck does that even mean? This video is not an explanation. It is a description of what you are doing. Filling out a table. Where does this table add together elements of the source array to compare them to the largest #? The Trues and Falses have to relate to some sort of hard math, not 'just because'.
Additionally, I thought that using .apply() was to be avoided? Given the various ways you could go about getting that largest number, why use apply at all instead of something like

` arr.sort(function(a,b){return a-b;}).pop() `

?
boberto

commented on 08/13/16

0

Could anyone translate the last updated solution to JavaScript? I don't know python.

noHands

commented on 01/15/17

0

It's a bit disgraceful that --on this paid service-- this solution is still up, months after it's been shown to be incorrect.
Just use as input: [11, 10, 1, -2]
(By the way, why isn't `sum` just a separate parameter?)

mhelvens

commented on 06/24/17

Log in to submit a comment.