Interview Questions

Subset sum problem

The subset sum problem is an important problem in computer science. Below we'll provide a simple algorithm 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.
## Simple (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:
## 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.
## Revision Note

There was an older article on Coderbyte which had a more efficient solution to this problem, but it was incorrect when dealing with negative numbers. A user provided an updated, correct solution in Python in the comment section of that post which can be viewed 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/

[]
[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) We loop through each element in the array and add it to every element in the power set.
(3) Then we take the union of these two sets.
(4) Once we get the power set, we check to see if the sum equals our goal S.

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

mrdaniel
published this on 7/16/17 **|**

11

This is not going to be good enough at the interview, you need to know dynamic programming approach, here is my Javascript code that deals with negative numbers and it's better than naive solution:

function ArrayAddition(arr) { var mp = { 0: 1 }; arr = arr.sort(function(a, b){return a-b}); var mx = arr[arr.length - 1]; for (var i = 0; i < arr.length - 1; i++) { var keys = Object.keys(mp); //console.log(keys, arr[i]); for (var j = 0; j < keys.length; j++) { var next = parseInt(keys[j]) + arr[i]; if (next == mx) { return true; } else if(next < mx && next > (0 - (arr.length - i - 1) * mx)) { mp[next] = 1; } } } return false; }

eleph

commented on 08/23/17

2

Given:
List = [1,1,2,3,4]
N = 5
Answer:
[[1, 1, 3], [1, 3, 1], [1, 4], [2, 3], [3, 1, 1], [3, 2], [4, 1]]
The code is not ideal :)

def subset_sum_problem_help(number, hashed_array, hash_store, used): if (number == 0): hash_store[tuple(used)] = used elif(number > 0): for each in hashed_array: for i in range(int(hashed_array[each])): new_hashed_array = hashed_array.copy() new_hashed_array[each] -= 1 new_num = number - each subset_sum_problem_help(new_num, new_hashed_array, hash_store, used + [each]) def subset_sum_problem(arr, num): hash_store = {} hashed_array = {} for each in arr: if(each not in hashed_array): hashed_array[each] = 1 else: hashed_array[each] += 1 subset_sum_problem_help(num, hashed_array, hash_store, []) return list(hash_store.values())

YerassylDanay

commented on 12/01/18

2

I'd like to know what makes eleph's solution dynamic? Could the map simply be an array? Do you need the last else-if to do more than the next < mx? Thanks eleph- LMK your thoughts ( comment through your logic please)

NeuTrix

commented on 09/01/17

-1

This is my solution using a hash table it can be solved in O(n) time:

def subsetProb(setX, s): seen = {} for i in range(0,len(setX)): a = setX[i] b = s - a if b in seen: return [a,b] else: seen[a] = a

bterryjack

commented on 09/29/17

Log in to submit a comment.