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

Question

I am working on an interview question that looks like this:

Given an array of integers and sums, check to see if any combination is added to the sum.

What programming method is used when they want to try all possible combinations of dialing?

Even if this is not the best solution to this problem, I run into problems when I need to either generate or do something with all the combinations of the list, and I would like to know how to handle it.

Answer 1

One convenient understanding is to understand that the binary representation of all numbers from 0 to (2^N)-1 is actually a set of bit masks for possible combinations of N individual elements. For example, for N=3 (3 elements) and therefore (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 easy to go through all the possible choices in a given order (so it's impossible to skip or double any possible choices).

Answer 2

There are several ways to solve this problem. One of them is the classic DP solution that others have posted. I am going to post a solution that uses only O (S) memory, where S is the sum of all the integers in the array (can be changed to denote the desired amount), and another that uses a very efficient randomized algorithm that can be tested to be very fast even for hundreds of thousands of numbers of any size and even rational and negative numbers.

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

 //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. 

Pseudo-code for a randomized algorithm: Let Used Used = list of numbers that you sum. Let Unused = a list of numbers you DO NOT summarize. Let tmpsum = 0. Let S = the desired amount that you want to achieve.

 for ( each number x you read ) toss a coin: if it 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 

It will be much faster than a dynamic programming solution, especially for random inputs. The only problems are that you cannot reliably detect when there is no solution (you can let the algorithm work for several seconds, and if it does not end, suppose there is no solution) and you cannot be sure that you will get the solution with minimum number of items selected. Again, you can add some logic to keep the algorithm going and trying to find a solution with fewer elements until certain stopping conditions are met, but that will make it slower. However, if you are only interested in a working solution, and you have a lot of numbers, and the desired amount can be VERY large, this is probably better than the DP algorithm.

Another advantage of this approach is that it will also work for negative and rational numbers without any changes, which is not true for the DP solution, since the DP solution involves the use of partial sums as array indices, and the indices can be natural numbers. Of course, you can use hashtables, but that will make the DP solution even slower.

To generate all combinations, you should look for 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 must run it on paper for a small number of elements to see how it works. You can optimize it by calculating the amount when you go, thereby avoiding the final summation. This is a general idea.

Answer 3

This does not answer your “combined” question, but this is probably the optimal solution to the question: P

This is a subset of the problem with the sum of the problem where you need to look for N sums.

The sum of the subset has a pseudopolynomial algorithm using dynamic programming:

psuedocode from this link

 Subset-Sum-Solver[S = w1,w2, . . . ,wn,B] 1 Initialize M[0..n, 0..B] everywhere False apart from M[0, 0] = True 2 for i from 1 to n do 3 for w from 0 to B do 4 M[i,w] = M[i − 1,w] _M[i − 1,w − wi] (any reference outside the array returns false) 5 Output M[n,B] 

where B is the sum, S is the set of numbers, n is the cardinality S (the number of elements in S), and M is the matrix n by B. This algorithm is O (nB)

In case of an interview question, do this for each sum, and you will get an algorithm that O (nmB), where m is the number of sums that you should check.

The question is a bit ambiguous, an array of integers used to get subsets of the same array of sums as well? those. does a subset of integers in array A also add up to one of the integers in array A? in this case, the algorithm is O (n ^ 2B), since n == m

Answer 4

Some help with terminology is needed here. Combinations are used to denote elements of k from a set of elements n , where the order of elements of k does not matter. A related concept of selecting elements k from a set of elements n , where the order of elements k matters, is called a permutation .

What do you initially say, however:

Given an array of integers and sums, check to see if any combination adds the sum.

- another thing - there is no fixed k : you are interested in any subset of the sizes of the original elements.

The set of all subsets of the set S is called the power collection of S, and there is a very simple formula for the number of elements contained in it. I will leave this as an exercise - as soon as you process it, it should be relatively obvious how to list the elements of the set of given parameters.

(Hint: The power set { 1, 2 } is { {}, { 1 }, { 2 }, { 1, 2 } } )

Answer 5

Recursive. The pseudocode will be something like this:

 function f(set,currentelement,selectedelements,sum,wantedsum) { for (thiselement=currentelement+1 to lastelement) { if (sum+thiselement==wantedsum) print out selectedelements+thiselement; if (sum+thiselement<wantedsum) { f(set,thiselement,selectedelements+thiselement,sum+thiselement,wantedsum); } } 

Answer 6

This sounds like a classic recursion problem. You start with the first element and look at the rest of the array; for each item, either it is selected or not. The main case is when the starting index is greater than the length of the array. Something like

 public static bool canSum(int start, int[] array, int sum) { if (start >= array.Length) return sum == 0; return canSum(start + 1, array, sum - array[start]) || canSum(start + 1, array, sum); } 

Answer 7

If you have positive and negative integers, you will encounter a combinatorial explosion, where any algorithm you choose will slow down with a fixed percentage for each increase in the length of your array. (If you have only positive integers, you can link your search after exceeding the target amount.)

Border Question: Is reuse of integers allowed?

You should look for "combinatorial algorithms." Knuths' tome-in-progress can help you quite a bit if you want to delve into the question.

Answer 8

I see two options:

• Compute the power set of the input array and check the sum of each element in the power set (see http://en.wikipedia.org/wiki/Power_set ). This is probably O (2 ^ N) and not good for large N
• Try something with a 0-1 Knapsack issue (see http://en.wikipedia.org/wiki/Knapsack_problem ). This should either find the largest amount less than your desired value, the amount that is your desired value, or find nothing. Based on the results, you can answer your original question. 0-1 A backpack is good because it works in polynomial time O (N ^ c), where c is constant. I don’t remember if it works for negative numbers.

Answer 9

If you really want to compute a set of functions, this can be done quite simply functionally.

Haskell has subsequence functions that essentially return the parameter set of any set as a list of lists.

Or you yourself can write

 powerSet :: [a] -> [[a]] powerSet [] = [[]] powerSet x:xs = map (:x) (powerSet xs) ++ (powerSet xs)