Updated：subsetSum

Question

試圖爲subsetSum編寫算法...它應該找到給定向量的所有可能的子集，然後找到哪些加起來到目標值。但是，我不斷收到nullpointerexceptions和其他一些錯誤。有人可以幫我嗎？我處於緊張的狀態，大腦幾乎沒有運作。非常感激。 謝謝。

java.lang.NullPointerException 
at Sumation.subsetSum(Sumation.java:78) 
at Sumation.main(Sumation.java:110) 

78行是在subsetSum方法中循環的第一行。

/* Ruben Martinez 
* CS 210 Data Structures 
* Program requires no paramters at main method call; 
* instead, a JOptionPane asks for the ints the user 
* wishes to search. These must be seperated by commas, 
* e.g. 50,40,30 or 35,45,55. Program then asks for a 
* target int to find. Program searches for target 
* and returns combinations that add up to the target. 
*/ 

import java.util.Vector; 
import javax.swing.*; 

public class Sumation 
{ 
    static int[] array; 
    static int target; 
    static Vector<Integer> subsets; 
    static Vector<Integer> set; 
    static Vector<Vector<Integer>> outer; 

    public Sumation() { 
     //insert integers into array 
     String defineArray = (String)JOptionPane.showInputDialog(null, 
       "Enter integers to search. Seperate by commas.", null); 
     //splits string into array delimeted by commas 
     String[] arrayString = defineArray.split(","); 
     //creates int array of size of string array 
     array = new int[arrayString.length]; 
     //adds ints from args[] to int array 
     for (int i = 0; i < arrayString.length; i++) { 
      array[i] = Integer.parseInt(arrayString[i]); 
     } 
     //enter integer to search for 
     String targetString = (String)JOptionPane.showInputDialog(null, 
       "What is your target integer?", null); 
     //turns string to int 
     target = Integer.parseInt(targetString); 


     set = new Vector<Integer>(); 
     for (int n = 0; n < array.length; n++) { 
      set.add(array[n]); 
     } 
    } 

    private static Vector<Vector<Integer>> getSubsets(Vector<Integer> set) { 
     Vector<Vector<Integer>> subsetCollection = new Vector<Vector<Integer>>(); 

     if (set.size() == 0) { 
      subsetCollection.add(new Vector<Integer>()); 
     } else { 
      Vector<Integer> reducedSet = new Vector<Integer>(); 
      reducedSet.addAll(set); 

      int first = reducedSet.remove(0); 
      Vector<Vector<Integer>> subsets = getSubsets(reducedSet); 
      subsetCollection.addAll(subsets); 

      subsets = getSubsets(reducedSet); 

      for (Vector<Integer> subset : subsets) { 
       subset.add(0, first); 
      } 

      subsetCollection.addAll(subsets); 
     } 

     return subsetCollection; 
    } 

    public static Vector<Vector<Integer>> subsetSum(Vector<Integer> subsets, int target) { 
     //creates outer vector 
     outer = new Vector<Vector<Integer>>(); 

     for (int k = 0; k < subsets.size(); k++) { 
      //if k is the target, display 
      if (array[k] == target) { 
       //creates new inner vector for values that equal target 
       Vector<Integer> inner = new Vector<Integer>(); 
       outer.add(inner); 
       //add k to vector 
       inner.add(array[k]); 
      } 
      for (int l =0; l < subsets.size(); l++) { 
       int sum = subsets.elementAt(k); 
       if (sum == target) { 
        //creates new inner vector for values that sum up to target 
        Vector<Integer> inner = new Vector<Integer>(); 
        outer.add(inner); 
        //add l,k to vector 
        inner.add(array[l]); 
        inner.add(array[k]); 
       } 
       else { 
        System.out.print(""); 
       } 
      } 
     } 
     //return combinations that add up to target in vector form 
     return outer; 
    } 

    public static void main(String[] args) { 
     //calls sumation constructor 
     Sumation s = new Sumation(); 
     s.getSubsets(set); 
     s.subsetSum(subsets, target); 
     JOptionPane.showMessageDialog(null, "The combinations that equal to "+target+" are \n"+outer, "Vector", JOptionPane.INFORMATION_MESSAGE); 
    } 
} 

Answer 1

你是怎麼試着分析這個的？

如果您手邊有一個調試器（即IDE），那麼分析這樣的問題非常容易。根據你的喜好，你可以

• 逐步完成從啓動程序完成
• 上設置斷點，在異常的拋出
• 設置一個斷點爲NullPointerExceptions

，並在該行所有的情況下，你會很容易地看到變量/字段的狀態是全部點。如果進入意想不到的狀態，倒回或重新運行程序很容易，以查看以前計算的結果並觀察它與預期偏離的位置。

即使你沒有調試器，你也可以每隔一段時間（肯定在異常行之前）放置println語句，以便看看這些值是什麼 - 一個窮人的調試器。

但是，嚴重的是，如果你打算做任何不平凡的Java開發，那麼請設置一個真正的調試器。如果花費5-20分鐘，並且比第一次調查這樣的問題時節省更多。

---

無論如何，問題的事實，你永遠不指定任何內容到subsets場造成的，所以它的null當你將它傳遞到subsetSum在main。

這可能是因爲getSubsets方法中的局部變量給它蒙上了陰影 - 如果你期待這種方法修改字段，那麼你會錯誤的。但是，無論如何，這將是一個不好的做法（恕我直言），因爲在遞歸方法中改變狀態會很容易出錯，即使正確也會導致很難在任何時候推斷該類， d需要知道它處於什麼狀態）。將結果賦給字段是一個常見的初學者的錯誤（可能是因爲它感覺更面向對象？），當更好的選擇是讓方法返回的結果時，它通常會存儲在局部變量中。

所以main方法應該分配getSubsets調用一個局部變量的結果，然後通過是到subsetSum方法。我注意到這些類型並不完全兼容 - 你確定subsetSum的參數也不應該是​​嗎？目前看起來你只能傳入一個子集，但這是一個不同的問題。）