陷入组合问题
我和我的程序有问题。 我已经提取了一组数据，我想测试是否有特定数字的组合。 例如，我有一个int数组，1 2 3 4 5，我想知道是否有7个组合，它必须回答是有3 + 4。
我发现我需要使用组合配方。 所以我认为外环可能像5C1..5C2..5C3..etc，开始“取1”然后“取2”一次找出所有可能的组合。 问题是我坚持如何在实际代码中实现这一点。
我对数学并不是很了解，定义的循环结构确实会有所帮助。
非常感谢提前！
这是一个从整数列表中获取所有可能总和的方法：
public static void getAllPermutations(final List data, final Set 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 (holder)){ holder.add(first.intValue() + item.intValue()); } } holder.add(first); } 用法：
List data = Arrays.asList(1, 2, 3, 4, 5, 6); Set permutations = new TreeSet (); getAllPermutations(data, permutations); System.out.println(permutations);
输出：
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]
虽然此解决方案不会为您提供导致总和的操作数，但它将包含1到1 + 2 + 3 + 4 + 5 + 6
对于这个问题有一个简单的伪多项式时间动态规划，首先确定可以丰富1然后为和2我们有两个选项，使用一个数组项，或使用之前创建的1加上新元素，就可以完成这个二维表最多可以满足要求的数量：
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]; }
这是O（n * Sum）。 实际上足以检查O(n*given_number) 。
快速而肮脏的解决方案可能是创建一个2D数组，其索引（在两个维度中）是数组中数字的位置，值是组合。 像这样的东西：
//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
如果您现在想要找到6的组合，您可以检查所有值并获得等于6的值的x和y索引。（在示例中：0 / 2,1 / 1和2/0）。 然后查找原始数组中那些索引处的数字（例如0/2 - > 1和5,1 / 1 - > 3和3,2 / 0 - > 5和1）。
请注意，这是一种快速且非常不稳定的方式（特别是对于较大的数组）并且可能返回比您想要或需要的更多排列（0/2和2/0对于操作add是相同的）。 然而，这应该适用于许多可能的操作，例如，对于x = 1，y = 5（结果：1）和x = 5，y = 1（结果：5），x y将是不同的。