Interview Questions

  • View all algorithm tutorials
  • blank
  • 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

    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(2n) 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 2n 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.
    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])      
    
    Run Code
    Run Code

    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/
    mrdaniel published this on 2/5/16 | subset, array, matrix, Microsoft, Google
    Comments
  • +
  • 19
  • -
  • dude, the video is not clear. I normally love your stuff but this one is an anomaly.
  • +
  • 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.
  • +
  • 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?
  • +
  • 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.
  • +
  • 2
  • -
  • Is this a legitimate question to expect for a coding bootcamp interview? Asking because it's on coderbyte's preparatory coursework for Makersquare.
  • +
  • 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.
  • +
  • 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++)
  • +
  • 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.
  • +
  • 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.
  • +
  • 1
  • -
  • Video is super confusing. Also negative numbers workaround does not work!
  • +
  • 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() ?
  • +
  • 0
  • -
  • Could anyone translate the last updated solution to JavaScript? I don't know python.
  • +
  • 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?)
    Log in to submit a comment.