What technique do I use for when I want to check all possible combinations of a set?

Question

I'm working through an interview question that goes like:

Given an array of integers and sum, check whether any combination adds up to the sum.

What programming technique does one use when they want to try all possible combinations of a set?

Even if that isn't the best solution to this problem, I come across problems where I need to either generate or do something with all combinations of a list, and I'd like to know how to handle that.

Answer 1

One handy insight is to realize that the binary representation of all numbers from 0 to (2^N)-1 is actually a set of bit masks for the possible combinations out of N distinct items. For instance, for N=3 (3 items) and thus (2^3)-1 = 7:

0: 000 = none
1: 001 = third item
2: 010 = second item
3: 011 = second and third items
4: 100 = first item
5: 101 = first and third items
6: 110 = first and second items
7: 111 = all 3 items

This makes it very easy to loop through all possible selections in a set order (so that it's impossible to skip or double-visit any potential selection).

Answer 2

There are multiple ways of solving this problem. One is the classical DP solution which others have posted. I'm going to post a solution that uses only O(S) memory, where S is the sum of all integers in the array (can be changed to mean the desired sum too) and another that uses a very efficient randomized algorithm that can be tested to be very fast for even hundreds of thousands of numbers of any size, and even rational and negative numbers.

DP solution in O(nS) time and O(S) memory:

//let F[i] = 1 if we can get sum i and 0 otherwise
F[0] = 1; // we can always make sum 0
for ( int i = 1; i <= n; ++i )
  for ( int j = S; j >= numbers[i]; --j )
    F[j] |= F[j - numbers[i]]; // basically, if F[j - numbers[i]] == 1, then we 
                               // can add numbers[i] to make F[j] 1, otherwise 
                               // we can't. A bitwise or operation will save us 
                               // an if/else structure basically.

Pseudocode for randomized algorithm: Let Used = list of numbers that you sum. Let Unused = list of numbers that you DON'T sum. Let tmpsum = 0. Let S = desired sum you want to reach.

for ( each number x you read )
  toss a coin:
    if it's heads and tmpsum < S
      add x to Used
    else
      add x to Unused

while ( tmpsum != S )
  if tmpsum < S 
    MOVE one random number from Unused to Used
  else
    MOVE one random number from Used to Unused

print the Used list, containing the numbers you need to add to get S

This will be much faster than the dynamic programming solution, especially for random inputs. The only problems are that you cannot reliably detect when there is no solution (you could let the algorithm run for a few seconds and if it doesn't finish, assume there is no solution) and that you cannot be sure you will get the solution with minimum number of elements chosen. Again, you could add some logic to make the algorithm keep going and trying to find a solution with less elements until certain stop conditions are met, but this will make it slower. However, if you are only interested in a solution that works and you have a LOT of numbers and the desired sum can be VERY big, this is probably better than the DP algorithm.

Another advantage of this approach is that it will also work for negative and rational numbers with no modifications, which is not true for the DP solution, because the DP solution involves using partial sums as array indexes, and indexes can only be natural numbers. You can of course use hashtables for example, but that will make the DP solution even slower.

To generate all combinations, you should look up backtracking: http://en.wikipedia.org/wiki/Backtracking

For this problem, you need to use something like this:

void back(int k)
{
  if ( k > numElements )
  { 
    // add all the nums[i] for which st[i] == 1 and check
    // if their sum is what you desire, then return;
  }

  for ( int i = 0; i <= 1; ++i )
  {
    st[k] = i;
    back(k + 1);
  }
}

You should run it on paper for small number of elements to see how it works. You can optimize it by calculating the sum as you go, thus avoiding the final summation. This is the general idea.