Stuck with Combination Problem

问题:

I'm having a problem w/ my program. I have extracted a set of data and I would like to test if there is a combination for a particular number. For example, I have an array of int, 1 2 3 4 5, I would like to know if there is a combination for 7 maybe, and it must answer yes there is 3 + 4.

I figured out that I need to use the combination formula. So I thought that the outer loop may go like 5C1..5C2..5C3..etc, starting to "take 1" then "take 2" at a time to find out all the possible combinations. The problem is I'm stuck at how to implement this in actual codes.

I'm not really very good with Math, A defined loop structure would really help.

Thanks a lot in advance!

回答1:

Here is a method that gets all possible sums from a List of Integers:

public static void getAllPermutations(final List<Integer> data,
    final Set<Integer> holder){

    if(data.isEmpty()){
        return;
    }
    final Integer first = data.get(0);
    if(data.size() > 1){
        getAllPermutations(data.subList(1, data.size()), holder);
        for(final Integer item : new ArrayList<Integer>(holder)){
            holder.add(first.intValue() + item.intValue());
        }
    }
    holder.add(first);
}

Usage:

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6);
Set<Integer> permutations = new TreeSet<Integer>();
getAllPermutations(data, permutations);
System.out.println(permutations);

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]

---

While this solution won't give you the operands that lead to the sum, it will include anything from 1 to 1 + 2 + 3 + 4 + 5 + 6

回答2:

There is a simple pseudo polynomial time dynamic programming for this problem, first determine is possible to rich 1 then for sum 2 we have two option, use one of a array items, or use previous founded 1 add up with new element, you can complete this 2 dimensional table upto rich the requested number:

bool findNode( int[] C , int givenNumber) {
 // compute the total sum
 int n = C.Length;
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 return T[givenNumber];
}

This is O(n*Sum). in fact is enough to check to O(n*given_number).

回答3:

A quick and dirty solution might be to create a 2D-Array whose index (in both dimensions) is the position of the number in the array and the values are the combinations. Something like this:

//int i[] = { 1, 3, 5}, operation is 'add'
//you have a 3x3 array here:
//\ |1 3 5    <- the original values at their corresponding indices for quick reference, the array is the bottom right 3x3 matrix
//--+------
//1 |2 4 6    
//3 |4 6 8
//5 |6 8 10

int[][] a = new int[3][3];
//in a loop fill the array

If you now want to find the combinations for 6, you could check all values and get the x and y indices for values that are equal to 6. (In the example: 0/2, 1/1 and 2/0). Then lookup the numbers at those indices in the original array (e.g. 0/2 -> 1 and 5, 1/1 -> 3 and 3, 2/0 -> 5 and 1).

Note that this is a quick and quite imperformant way (especially for bigger arrays) and might return more permutations than you want or need (0/2 and 2/0 is the same for operation add). However, this should work for many possible operations, e.g. x^y would be different for x=1, y=5 (result: 1) and x=5, y=1 (result: 5).