回溯 - 給定一組數字，找出總和等於M的所有子集（M給出）

Question

正如標題所說，我們得到一組數字，我們必須找到所有子集的總和相等到給定的數字（我們稱它爲M）。

你們中的大多數人可能已經對這個問題很熟悉了，所以讓我們開始追逐。我最近剛剛進入回溯計劃（我得告訴你，我到目前爲止已經完全崩潰了），這就是爲什麼我想要解決更多「經典」問題。

現在，在下面你會看到我的代碼試圖以回溯的方式解決這個問題。但是，代碼給出線程

異常「主要」 java.lang.StackOverflowError的

第44行（我有它突出顯示），還，我真的不知道，如果它真的以回溯方式解決問題，或者如果我的代碼只是完整和徹底的便便。

package project3; 

import java.util.*; 

public class Main { 
    static int[] A = { 1, 2, 3, 4 }; // the array in which we are given the numbers.-> 
    static int n = A.length; // -> I have it filled with 1, 2, 3, 4 for testing purposes 
    static int m = 5; // the number which the subsets' sum must be 
    static int[] Sol = new int[50]; // the array in which solutions are stored up-> 
          //->until they are syso'ed, after that it gets zero'ed 
    static void makeZero() {   // make the solution array 0 again 
     for (int i = 0; i < 50; i++) 
      Sol[i] = 0; 
    } 

    static void show() { // outputs the solution array 
     int i = 0; 
     while (Sol[i] != 0 && i < 49) { 
      System.out.print(Sol[i] + " "); 
      i++; 
     } 
    } 

    public static void main(String[] args) { 
     Sol[0]=A[0]; back(0, 1, A[0], 1);// we start with the first number in the array as-> 
    }      // -> both the first element as the solution and part of the sum 

    static int back(int i, int j, int S, int nr) { 
     if (i < n && j < n) { 

      if (A[j] + S == m) {// if we got a solution, we output it and then go to the -> 
       Sol[nr] = A[j]; // -> next element if possible, if not, we start again with -> 
       show();   // -> the following element 
       if (j < n - 1) 
        back(i, j++, S, nr); 
       else if (i < n - 1) { 
        makeZero(); 
        back(i + 1, i + 2, 0, 0); 
       } 
      } 

      else if (A[j] + S > m) { // condition for stoping and starting over with another element 
       if (j < n - 1) // we try again with the following element 
        back(i, j++, S, nr);// LINE 44 : Exception in thread "main" java.lang.StackOverflowError 
       else if (i < n - 2 && j == n - 1) { // if not possible, we start again with the following element 
        makeZero(); 
        back(i + 1, i + 2, 0, 0); 
       } else if (i == n - 2 && j == n - 1) // if we are down to the last element-> 
        if (A[i + 1] == m)    // ->we check if it is ==m 
         System.out.println(A[i + 1]); 
       } 


      else if (j < n - 1 && A[j] + S < m) { // obvious 
       Sol[nr++] = A[j]; 
       S = S + A[j]; 
       back(i, j + 1, S, nr); 
      } 

      else if (j == n - 1 && A[j] + S < m && i < n - 2) {// if the sum!=m and the are no more elements-> 
       makeZero();         // ->start again with another element 
       back(i + 1, i + 2, 0, 0); 
      } 
      else { // if we are down to the last element, we check if it is ==m 
       if(A[i+1]==n-1) 
        System.out.println(A[i + 1]); 
      } 

     } 

     return 0; 
    } 

} 

注：我希望我的意見是有益的，但如果他們是不是幫助不理會他們更加混亂，我認爲你可以得到做什麼我沒有他們的想法。然而，我想知道爲什麼代碼給出了這個錯誤（我知道在什麼情況下通常給出錯誤，但我不明白爲什麼我在這裏得到它，因爲我不能看到任何無限循環）以及如何使代碼工作，以及它是否回溯。

Answer 1

爲了找到沒有達到堆棧溢出錯誤的所有子集，我強烈建議不要使用遞歸。使用遞歸通常會在運行時產生很多開銷。這種開銷導致堆棧溢出錯誤。您應該使用更穩定的算法方法/設計，稱爲動態編程。

Dynamic Programming Example應該告訴你如何把握你現在擁有的東西並將其轉化爲動態編程概念。