java回溯并查找数组中等于某个值k的所有子集

Question

我之前问过question，当我去终端编码时，我想我明白了，我又一次完全迷路了。我的问题是我有一些数组，比如[1,2,3,4]，我需要找到所有可能的组合，它们将等于目标值5

我知道这是一种回溯方法。我无法在线获取它，因为很多解决方案都在我的脑海中浮现。我只需要一个简单的解释或一个非常小的数组的一步一步的跟踪来可视化正在发生的事情

我在图书馆里呆了12个小时，现在我感到非常沮丧，因为我无法理解它，我也希望能有一个简单的方法。此外，除了C或java之外，我对许多语言都不熟悉

Answer 1

你们已经掌握了Subset Sum Problem的一个变体。不幸的是，这个问题是NP完全问题，所以如果你希望得到一个快速的（多项式）解决方案，那你就倒霉了

也就是说，如果您的数组相当小，并且值相当小，那么暴力解决方案可能仍然足够快

import java.util.Arrays;
import java.util.LinkedList;


public class SubsetSum {

    /** Helper for the power set generating function.
     *  Starts with a partially built powerSet pSet that includes
     *  numbers with index 0 ... i. For every element in the current power set
     *  Create a new array that is equivalent to the existing array plus it has
     *  the i+1th number (n) concatinated on the end.
     * @param pSet - The completed pSet for a smaller set of numbers
     * @param n - The number of add to this pSet.
     * @return a reference to pSet (not necessary to use). When returning,
     * pSet will have double the size it had when the method began.
     */
    private static LinkedList<Integer[]> addNumb(LinkedList<Integer[]> pSet, int n){
        LinkedList<Integer[]> toAdd = new LinkedList<>();
        for(Integer[] arr : pSet){
            Integer[] arr2 = new Integer[arr.length+1];
            for(int i = 0; i < arr.length; i++){
                arr2[i] = arr[i];
            }
            arr2[arr.length] = n;
            toAdd.add(arr2);
        }

        //Add all of the toAdds to the pSet
        pSet.addAll(toAdd);
        return pSet;
    }

    /** Creates the power set for the given array of ints.
     * Starts by creating a set with the empty array, which is an element of every
     * power set. Then adds each number in the input array in turn to build the final
     * power set.
     * @param numbs - the numbers on which to build a power set
     * @return - the power set that is built.
     */
    private static LinkedList<Integer[]> makePowerSet(int[] numbs){
        LinkedList<Integer[]> pSet = new LinkedList<Integer[]>();
        //Add the empty set as the first default item
        pSet.add(new Integer[0]);

        //Create powerset
        for(int n : numbs){
            addNumb(pSet, n);
        }

        return pSet;
    }

    /** Returns the simple integer sum of the elements in the input array */
    private static int sum(Integer[] arr){
        int i = 0;
        for(int a : arr){
            i += a;
        }
        return i;
    }


    /** Brute-forces the subset sum problem by checking every element for the desired sum.
     */
    public static void main(String[] args) {
        int[] numbs = {1,2,3,4,5,6,7,8}; //Numbers to test
        int k = 7;                 //Desired total value

        LinkedList<Integer[]> powerSet = makePowerSet(numbs);

        for(Integer[] arr : powerSet){
            if(sum(arr) == k)
                System.out.println(Arrays.deepToString(arr));
        }
    }

}

Answer 2

事实上，有一个关于回溯等的故事

让我们来看一个更复杂的例子：

我们想要达到的值是11，数组是[5,4,8,2,3,6]

以下是一种可能的算法：

我们将列出我们找到的所有方法，以达到每一个小于或等于11的可能数字（我不会谈论我们使用的结构或任何东西，因为我只是解释算法，而不是它的实现）

我们将从零开始，并同时考虑一个新的数字。在这个算法中，我会考虑数组中的每一个数字都是正的，所以我不会跟踪到达比我们想要达到的数字高的数字。p>

所以一开始我们什么都没有

我们介绍我们的第一个号码：5

因此，我们有一种方法可以达到5，即5（或5+0，如果您愿意）

我们介绍我们的第二个号码：4 我们现在可以达到的数字是：

4:{4}
5:{5}
9:{4+5}

我们介绍我们的第三个号码：8 我们现在可以达到的数字是：

4:{4}
5:{5}
8:{8}
9:{4+5}

仅此而已，因为8+4>；十一,

我们介绍我们的第四个号码：2 我们现在可以达到的数字是：

2:{2}
4:{4}
5:{5}
6:{4+2}
7:{5+2}
8:{8}
9:{4+5}
10:{8+2}
11:{4+5+2}

我们介绍我们的第五个号码：3 我们现在可以达到的数字是：

2:{2}
3:{3}
4:{4}
5:{5 ; 2+3}
6:{4+2}
7:{5+2 ; 4+3}
8:{8 ; 5+3}
9:{4+5 ; 4+2+3}
10:{8+2 ; 5+2+3}
11:{4+5+2 ; 8+3}

我们介绍我们的第六个号码：6 我们现在可以达到的数字是：

2:{2}
3:{3}
4:{4}
5:{5 ; 2+3}
6:{4+2 ; 6}
7:{5+2 ; 4+3}
8:{8 ; 5+3 ; 2+6}
9:{4+5 ; 4+2+3 ; 3+6}
10:{8+2 ; 5+2+3 ; 4+6}
11:{4+5+2 ; 8+3 ; 5+6 ; 2+3+6}

结论：11:4+5+2可分为4种方式；8+3 ; 5+6和2+3+6

Answer 3

下面是一些简单（但效率极低）的代码来解决这个问题

其中的“回溯”部分是通过递归实现的。每当您从Java中的一个方法返回时，您都会通过堆栈“回溯”到调用它的位置。这使得使用调用堆栈跟踪“回溯”状态变得非常容易

这是基本的想法。假设我正在某个数组A中搜索求和n。我们在索引i=0的数组中开始搜索。然后我们尝试两件事：

• 尝试将元素A[i]包含在运行总和中。我们通过从索引i+1搜索数组中的值n-A[i]来实现这一点。我们需要在包含元素的运行列表中记录此元素。我们将此列表称为运行总和中包含的所有元素xs
• 尝试不将元素A[i]包含在运行总和中。我们通过从索引i+1中搜索数组以查找n的当前值来实现这一点。因为我们没有包含[i]的xs，所以不需要更新xs

查看如何搜索整个数组中的第一个案例，回溯，然后再次搜索第二个案例

请注意，您需要在“回溯”后保留一份xs的副本，以便在第二次搜索中使用。我认为使用标准Java库实现这一点的最简单方法是在回溯时撤消对xs的更改。因此，如果您在xs的末尾添加一些元素x来执行“带”-搜索，那么只需在执行“不带”-搜索之前从xs中删除最后一个元素即可

我没有试图将所有答案存储在数据结构中，而是一找到答案就打印出来。这也是为了简化此解决方案的逻辑

import java.util.Deque;
import java.util.ArrayDeque;

public class SubarraySums {

    /** Program entry point */
    public static void main(String[] args) {
        int[] array = { 1, 8, 7, 9, 5, 2 };
        findSubarraySums(12, array);
    }

    /** Wrapper function for the search */
    public static void findSubarraySums(int goal, int[] array) {
        // Search the whole array with an empty starting set
        search(goal, new ArrayDeque<Integer>(), array, 0);
    }

    /** Helper for printing an answer */
    private static void printAnswer(Deque<Integer> xs) {
        // Print the sum
        int sum = 0;
        for (int x : xs) sum += x;
        System.out.printf("%d =", sum);
        // Print the elements
        for (int x : xs) {
            System.out.printf(" %d", x);
        }
        System.out.println();
    }

    /**
     * Search the array, starting from index i,
     * for a subset summing to n.
     * The list xs includes all of the elements that are already
     * assumed to be included in this answer
     */
    private static void search(int n, Deque<Integer> xs, int[] array, int i) {
        // Base case: we've reached zero!
        if (n == 0) {
            printAnswer(xs);
            return;
        }
        // Base case: solution not found
        if (n < 0 || i >= array.length) return;
        // Recursive case: try searching with and without current element
        // with:
        xs.addLast(array[i]);
        search(n-array[i], xs, array, i+1);
        // without:
        xs.removeLast();
        search(n, xs, array, i+1);
    }

}

上面的代码在数组中有6个元素，因此它将对search进行2个⁶=64个递归调用。这就是为什么它“超低效”的原因。但它也非常简单，所以这应该有助于你理解它。您应该使用调试器逐步检查代码以查看发生了什么，或者只是在一张纸上跟踪执行情况。在搜索过程中，执行如何“回溯”调用堆栈以尝试这两个选项（包括/不包括）应该是非常明显的

我在上面的代码中使用了ArrayDeque来存储我的xs列表，这仅仅是因为Deque接口具有addLast和removeLast方法。一个LinkedList也可以工作（因为它还实现了Deque接口）。一个ArrayList也可以，但是您需要使用add和remove(list.size()-1)，这有点冗长