-1

我正在尝试编写一个代码，将子集中的所有整数相加，看看它们是否加起来为零。这是我到目前为止所得到的

  /**
   * 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;
      }

  }

}

这是我收到的有关制作此代码的提示：

首先考虑集合的第一个元素，第一个元素和集合的其余部分是否存在零子集和？没有第一个和集合的其余部分，是否存在零子集和？如果 2 或 3 中的任何一个为真，则返回真，否则返回假

任何帮助，我一直在尝试一整天我无法让它为我的生活工作，在递归中我无法弄清楚如何自己调用该方法。

所以我的问题是我将如何在递归中编写这个方法？整个方法应该将子集的总和相加，看看它们是否等于零。

4

3 回答 3

0 
// 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;
            }
}
于 2013-03-26T02:24:27.800 回答
0

好的，您可以为递归做这样的事情

 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));
 }

我没有检查就输入了它，但这就是概念。玩弄这个想法

第一个电话应该是这样的 

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

// 好的，你也可以这样做...

    // 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);
    }

//现在你可以在某个地方做到这一点

     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;
            }
}
于 2013-03-26T01:35:29.200 回答
-1

和这个问题类似吗？以及如何解决？

给定一组整块重量的石头，可以将它们分成重量完全相等的 2 组。编写递归函数

public static boolean canSplit（int [] 石头，int left，int right）

其中，给定一组权重的石头意味着函数可以分为两组）left和right-（这样整个团队都是值得的。必要时使用函数subArray。训练：查看第一块石头并递归决定哪个组有与之相关联。

于 2015-01-06T12:12:29.397 回答