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

You need to be a premium member to see the rest of this question and code.

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

11

@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

10

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

ithoughtso

commented on 04/17/16

5

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

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

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

@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

@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

0

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

noHands

commented on 01/15/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

Login to submit a comment