Interview Questions

  • View all tutorials
  • blank
  • 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:
    [] [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.

    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.

    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/
    mrdaniel published this on 7/16/17 | subset, array, matrix, Microsoft, Google
    Comments
  • +
  • 4
  • -
  • 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;         
    }
    
  • +
  • 0
  • -
  • 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
    
  • +
  • 0
  • -
  • 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)
    Login to submit a comment