查找其总和等于给定目标的int数组的所有子集

我正在尝试实现以下功能：

给定目标总和，请从int数组中填充总和等于目标总和的所有子集。

例如：

目标总和为15。

int数组为{ 1, 3, 4, 5, 6, 15 }。

然后满足所有满足其总和的子集是15，如下所示：

15 = 1+3+5+6
15 = 4+5+6
15 = 15

我正在使用java.util.Stack类来实现此功能以及递归。

GetAllSubsetByStack类

import java.util.Stack;

public class GetAllSubsetByStack {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 15;

    private Stack<Integer> stack = new Stack<Integer>();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;

    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                sumInStack -= (Integer) stack.pop();
            }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }
}

主类

public class Main {

    private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
        14, 15 };

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}

控制台中的输出如下：

15 = 1+3+4+5+2
15 = 1+3+4+7
15 = 1+3+5+6
15 = 1+3+2+9
15 = 1+3+11
15 = 1+4+2+8
15 = 1+4+10
15 = 1+5+2+7
15 = 1+5+9
15 = 1+6+8
15 = 1+14
15 = 3+4+6+2
15 = 3+4+8
15 = 3+5+7
15 = 3+2+10
15 = 4+5+6
15 = 4+2+9
15 = 4+11
15 = 5+2+8
15 = 5+10
15 = 6+2+7
15 = 6+9
15 = 2+13
15 = 7+8
15 = 15

请帮我解决以下两件事：

如何改善此代码以减少递归时间？递归之前对int数组排序（从高到低）是否是更好的方法？
有没有一种方法可以在不使用递归的情况下改善代码？

#1 楼

这里有三个合理的答案：

是的，可以提高递归代码的性能。
是的，部分改进可以来自对数据进行排序。
是的，有一种方法可以将代码重构为不使用递归，甚至可以更快。

请记住，这个答案变得“复杂”。

当前代码的基本性能改进：

if (sumInStack == TARGET_SUM) {
    print(stack);
}

可以很容易地实现：

if (sumInStack >= TARGET_SUM) {
    if (sumInStack == TARGET_SUM) {
        print(stack);
    }
    // there is no need to continue when we have an answer
    // because nothing we add from here on in will make it
    // add to anything less than what we have...
    return;
}

我不喜欢任何递归函数依赖于外部（外部方法）值。您的情况是，sumInStack是外部的。另外，如果我们对数据进行排序，则可以得到一些好处，并且可以通过重构递归来减少工作量（自我们可以保证一点之后的所有值都具有某些属性...）：

考虑该方法（假设排序为data）：

public void populateSubset(final int[] data, int fromIndex, 
                           final int[] stack, final int stacklen,
                           final int target) {
    if (target == 0) {
        // exact match of our target. Success!
        printResult(Arrays.copyOf(stack, stacklen));
        return;
    }

    while (fromIndex < data.length && data[fromIndex] > target) {
        // take advantage of sorted data.
        // we can skip all values that are too large.
        fromIndex++;
    }

    while (fromIndex < data.length && data[fromIndex] <= target) {
        // stop looping when we run out of data, or when we overflow our target.
        stack[stacklen] = data[fromIndex];
        populateSubset(data, fromIndex + 1, stack, stacklen + 1, target - data[fromIndex]);
        fromIndex++;
    }
}

您可以使用以下函数调用此函数：

Arrays.sort(data); 
populateSubSet(data, 0, new int[data.length], 0, 15);

因此，那就是“代码可以改进吗？”和“将排序帮助”

至于系统的“展开”（无递归）版本，就可以做到。它需要三个int []数组：

int[] data = {....}
int[] sum = new int[data.length];
int[] indices = new int[data.length];
int depth = 0;
int lastindex = -1;

总和给出的和索引的作用就像一个堆栈，深度是堆栈的深度（再次假设是排序的）数据）：

Arrays.sort(data);
while (depth >= 0) {
    lastindex++;
    if (lastindex == data.length) {
        // we have run out of data.
        do {
            // walk up the stack till we find some data.
            depth--;
        while (depth >= 0 && (lastindex = indices[depth] + 1) < data.length);
    }
    if (depth >= 0) {
         .....
         you then add your code in here to check the target,
         keep it updated in your 'stack'.
         go down a level and move on....
    }

}

\ $ \ begingroup \ $
我能想到与记忆有关的许多很棒的事情！我们可以将所有解决方案存储在ArrayList >中，用于特定的对（fromIndex，目标）
\ $ \ endgroup \ $
– Vikrant Goel
2015年6月3日在8:22

#2 楼

解决此类问题的另一种方法-研究所有子集（即“功率集”的成员）的属性-将主集视为一个单元格列表，每个单元格都视为一个二进制数字位置。因此，可以用二进制数来描述幂集的成员，这样子集仅包含对应于二进制值1的幂集的那些元素。

这样做，您可以生成仅通过计数即可设定功率。当然，当原始集合中包含更多值可以由给定编程语言中的本机整数类型轻松处理时，这会变得有些复杂，但是Java具有BigInteger。（为任何目的枚举功率集对于原本庞大的功率集都会有点痛苦。）

#3 楼

我还没有完全解决，但是这里最好的算法可能是动态编程。基本上，我将对值进行排序，并考虑先前的总和，并保留所有可能的总和。

例如，对于输入{1、2、3、4、6}：

Value : possible sums considering earlier sums and current value
1     : 0, 1
2     : 0, 1, 2, 3     (that is: 1 + 0 * 2, 0 * 1 + 2, 1 + 2)
3     : 0, 1, 2, 3, 4, 5, 6
4     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11
6     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8, 12, 13, 15, 16

请注意，上面有一些效率是因为一些组合会重复很多次。例如，在第3项中，可以从（1 * 3_from_previous_sum + 0 * 3）或（0 * 3_from_previous_sum + 1 * 3）获得输出值3。您走得越远，出现的冗余值就越多。

我还没有算出这是否明显比使用蛮力搜索更有效，但我敢肯定。动态编程应该增加算法的内存需求，但要减少计算时间。

我制作的示例表将有助于回答是否可以达到给定的总和，但不能给出全部结果可以产生总和的组合（如果存在）。要回答第二个问题，必须修改表，使其也与每个输出总和值相关的所有组合都可以产生它。

编程黑洞网

查找其总和等于给定目标的int数组的所有子集

#1 楼

评论

#2 楼

#3 楼