申請子集總和

Question

遞歸遞歸我試圖做一個代碼，添加一個子集中的所有整數，看看他們加起來爲零。這裏就是我有這麼遠

/** 
    * Solve the subset sum problem for a set of integer values. 
    * 
    * @param t 
    *   a set of integer values 
    * @return <code>true</code> if there exists a non-empty subset of 
    *   <code>t</code> whose elements sum to zero. 
    */ 
    public static boolean subsetSum(Set<Integer> t) { 
    return subsetSum(new ArrayList<Integer>(t), null); 
    } 

    /** 
    * Computes the sum of two Integers where one or both references are null. If 
    * both references are null then the result is null; otherwise the result is 
    * an integer equal to <code>a + b</code> where null references are treated as 
    * being equal to zero. 
    * 
    * @param a 
    * @param b 
    * @return the sum of <code>a</code> and <code>b</code> 
    */ 
    private static Integer add(Integer a, Integer b) { 
    if (a == null && b == null) { 
     return null; 
    } else if (a == null) { 
     return b; 
    } else if (b == null) { 
     return a; 
    } 
    return a + b; 
    } 

    /** 
    * Recursive solution for the subset sum problem. 
    * 
    * <p> 
    * <code>currentSum</code> holds the value of the subset under consideration; 
    * it should be <code>null</code> if the current subset is empty. 
    * 
    * @param t 
    *   a list containing unique integer values (a set of integers) 
    * @param currentSum 
    *   the current subset sum so far 
    * @return <code>true</code> if there exists a subset of <code>t</code> such 
    *   that the sum of the elements in the subset and 
    *   <code>currentSum</code> equals zero. 
    */ 

******** THIS IS THE PART I HAD TO EDIT ************* 
    private static boolean subsetSum(List<Integer> t, Integer currentSum) { 
     currentSum = 0; 
     for (int i = 0; i < t.size(); i++) { 
      currentSum = currentSum + (Integer)(t.get(i)); 
     } 
     if (Lab9W.add(currentSum, t.get(0)) == 0) { 
      return true; 
     } 
     else if (Lab9W.add(currentSum, t.get(1)) == 0) { 
      return true; 
     } else if (Lab9W.add(-t.get(0),t.get(0)) == 0) { 
      return true; 
     } 
     else { 
      return false; 
     } 

    } 

} 

這裏有什麼提示，我已經收到有關使這個代碼：

consider the first element of the set first is there a subset sum of zero with first and the rest of the set? is there a subset sum of zero without first and the rest of the set? if either of 2 or 3 is true then return true, otherwise return false

任何幫助，請我一直在嘗試了一整天，我不能讓它開始工作對於我的生活，順利遞歸我不知道如何調用自己的方法。

所以我的問題是我將如何寫這種方法在遞歸？整個方法應該添加子集的總和，看它們是否等於零。

Answer 1

OK，你可以遞歸

private static boolean subsetSum(List<Integer> t, Integer sizeOfArray,Integer currentSum){ 

     if(sizeOfArray == -1) 
     { 
     if (Lab9W.add(currentSum, t.get(0)) == 0) 
     { 
      return true; 
     } 
     else if (Lab9W.add(currentSum, t.get(1)) == 0) 
     { 
      return true; 
     } 
     else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
     { 
      return true; 
     } 
     else 
     { 
      return false; 
     } 

     return subsetSum(t,sizeOfArray - 1,currentSum + t.get(sizeOfArray)); 
} 

做這樣的事情我檢查出來但這就是排序consept的鍵入它。玩arroud這個想法

第一個電話應該是這樣的

subsetSum(array,array.size()-1,0); // i dont know if its array.size()-1 // it is... 

// OK，你也可以做到這一點...

// return sum of array 
    public Integer subsetSum(List<Integer> t, Integer sizeOfArray) 
    { 
     if(sizeOfArray == 0) 
      return t.get(0); 
     return subsetSum(t, sizeOfArray - 1) + t.get(sizeOfArray); 
    } 

//現在你可以somewere做到這一點

 public boolean check(List<Integer> t) 
{ 
     Integer currentSum = subsetSum(t,t.size()-1); 

     if (Lab9W.add(currentSum, t.get(0)) == 0) 
      { 
       return true; 
      } 
      else if (Lab9W.add(currentSum, t.get(1)) == 0) 
      { 
       return true; 
      } 
      else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
      { 
       return true; 
      } 
      else 
      { 
       return false; 
      } 
} 

Answer 2

// return sum of array 
    public Integer subsetSum(List<Integer> t, Integer sizeOfArray) 
    { 
     if(sizeOfArray == 0) 
      return t.get(0); 
     return subsetSum(t, sizeOfArray - 1) + t.get(sizeOfArray); 
    } 
//now you can do this somewere 

    public boolean check(List<Integer> t) 
{ 
     Integer currentSum = subsetSum(t,t.size()-1); 

     if (Lab9W.add(currentSum, t.get(0)) == 0) // do something with these if statements 
      { 
       return true; 
      } 
      else if (Lab9W.add(currentSum, t.get(1)) == 0) 
      { 
       return true; 
      } 
      else if (Lab9W.add(-t.get(0),t.get(0)) == 0) 
      { 
       return true; 
      } 
      else 
      { 
       return false; 
      } 
} 

Answer 3

它與這個問題相似嗎？你如何解決它？

給定一組完整的重量石塊，可以將它們分成兩組，重量爲 完全相等。 寫遞歸函數

公共靜態布爾canSplit（INT []石頭，詮釋左，詮釋右）

其中，給定一組權重的石頭意味着功能可以分爲兩組），左 ，右 - （這樣整個團隊都是值得的，必要時使用subArray函數） 培訓：看看第一塊石頭並遞歸決定哪個組與它有關聯