2

所以给定一个数组，例如[3, 5, 7, 2]我想使用递归来给我所有可能的总和组合for example: 3, 5, 7, 2, 8(3+5),10(3+7),5(3+5)... 15(3+5+7)等。我不完全确定如何使用 java 来解决这个问题。

4

6 回答 6

3

数组中的每个数字都有两个选择。

  1. 使用号码

  2. 不要使用号码

    void foo(int[] array, int start, int sum) {
    if(array.length == start) return;
    int val = sum + array[start];
    //print val;
    foo(array, start + 1, val); //use the number
    foo(array, start + 1, sum); //don't use the number
}

最初的电话是foo(a, 0, 0)

于 2012-10-06T20:25:15.823 回答
0

对此的递归算法可以按如下方式工作：

列表的所有总和等于以下的并集：

  • 第一个数字加上没有第一个数字的子列表的总和
  • 没有第一个数字的子列表的总和

最终，您的递归调用将达到一个空列表的停止条件，该列表只有一个总和（零）

于 2012-10-06T20:19:58.533 回答
0

这是用伪代码执行此操作的一种方法：

getAllPossibleSums(list)
    if(list.length == 1)
        return list[0];
    otherSums = getAllPossibleSums(list[1:end])
    return union(
        otherSums, list[0] + otherSums);
于 2012-10-06T20:20:28.900 回答
0 
public static void main(String[] args) {
    int [] A = {3, 5, 7, 2};
    int summation = recursiveSum(A, 0, A.length-1);
    System.out.println(summation);
  }

  static int recursiveSum(int[] Array, int p, int q) {
    int mid = (p+q)/2; //Base case
    if (p>q) return 0; //Base case
    else if (p==q) return Array[p];
    **else
      return  recursiveSum(Array, p, mid) +  recursiveSum(Array, mid + 1, q);**
  }
于 2013-08-19T23:21:50.617 回答
0 
public static void main(String[] args) {
    findAllSums(new int[] {3, 5, 7, 2}, 0, 0);
}

static void findAllSums(int[] arrayOfNumbers, int index, int sum) {     
    if (index == arrayOfNumbers.length) {
        System.out.println(sum);
        return;
    }

    findAllSums(arrayOfNumbers, index + 1, sum + arrayOfNumbers[index]);
    findAllSums(arrayOfNumbers, index + 1, sum);
}

您有两个分支，一个在其中添加当前号码，另一个在其中不添加。

于 2012-10-06T20:32:18.390 回答
0

有史以来最简单的方法：

private int noOfSet;

添加以下方法：

private void checkSum() {
        List<Integer> input = new ArrayList<>();
        input.add(9);
        input.add(8);
        input.add(10);
        input.add(4);
        input.add(5);
        input.add(7);
        input.add(3);

        int targetSum = 15;
        checkSumRecursive(input, targetSum, new ArrayList<Integer>());

    }

    private void checkSumRecursive(List<Integer> remaining, int targetSum, List<Integer> listToSum) {
        // Sum up partial
        int sum = 0;
        for (int x : listToSum) {
            sum += x;
        }

        //Check if sum matched with potential
        if (sum == targetSum) {
            noOfSet++;
            Log.i("Set Count", noOfSet + "");
            for (int value : listToSum) {
                Log.i("Value", value + "");
            }
        }

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.size(); i++) {
            // Build list of remaining items to iterate
            List<Integer> newRemaining = new ArrayList<>();
            for (int j = i + 1; j < remaining.size(); j++)
                newRemaining.add(remaining.get(j));

            // Update partial list
            List<Integer> newListToSum = new ArrayList<>(listToSum);
            int currentItem = remaining.get(i);
            newListToSum.add(currentItem);
            checkSumRecursive(newRemaining, targetSum, newListToSum);
        }
    }

希望这会帮助你。

于 2016-09-17T15:39:40.007 回答