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

Question

我早些时候询问过question，我想我明白了，当我去我的终端代码时，我又一次完全迷失了。我的问题是我有一些数组说[1,2,3,4]，我需要找到所有可能的组合，将等于目标值5.

我明白这是一个回溯的方法。我无法像在线那样得到它，很多解决方案都在我头上，我只需要一个简单的解释或者一步一步地追踪一个非常小的数组来可视化发生的事情。

我已经在图书馆度过了最后的12个小时，现在我感到非常沮丧，因为我无法理解它，我也很欣赏一个简单的方法。此外，我不熟悉C或Java以外的其他语言。

Answer 1

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

这个“回溯”部分是通过递归实现的。每当从Java中的方法返回时，您都会“通过堆栈”回溯到从何处调用它。这使得使用调用堆栈来跟踪你的“回溯”状态非常简单。

这里的基本思想。假设我正在寻找一些数组A的总和n。我们在索引i = 0开始我们的搜索。然后，我们要做两件事情：

• 尝试包括元素A [1]在运行总和。我们通过从索引i + 1中搜索n-A [i]来完成此操作。我们需要在包含的元素的运行列表中记录这个元素。我们会将此列表包含在我们的运行金额xs中。
• 尝试不是包括运行总和中的元素A [i]。我们通过从索引i + 1中搜索当前值n来完成此操作。由于我们不包括A [i]我们不需要更新xs。

看看我们如何搜索整个阵列对于第一种情况，走回头路然后第二种情况做搜索一遍？

请注意，在第二次搜索中使用“backtracking”后，您需要保留一份xs。我认为使用标准Java库完成此操作的最简单方法是在回溯时撤销对xs的更改。因此，如果您在xs的末尾添加一些元素x以执行“with”搜索，那么只需在执行“without”搜索之前从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个元素，所以它将会使2 = 64递归调用search。这就是为什么它“超低效率”。但它也非常简单，所以应该帮助你理解它。您应该使用调试器逐步完成代码以查看会发生什么，或者只是在一张纸上查找执行情况。在搜索过程中，执行“回溯”调用堆栈以尝试两种选项（包括/不包含）应该是非常明显的。

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

Answer 2

您已经掌握了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 3

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

我们只是有点走更复杂的例子：

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

这是可能的算法中的一个：

我们会列出所有我们发现，以达到比较少或等于11每一个可能的号码一样（我赢了别说话关于我们使用的结构或任何东西，因为我只是解释算法，而不是它的实现）。

我们将从零开始，一次添加一个新号码。在这个算法中，我会考虑阵列中的每个数字都是正数，所以我不会追踪到达数量比我们想要达到的数字更高的数字。

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

我们推出了我们第一个数字：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> 11

我们推出了我们来回数：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} 

结论：有4种方法可以制作11：4 + 5 + 2; 8 + 3; 5 + 6和2 + 3 + 6