java - 一种递归算法来找到给定整数数组的每个可能的总和？

Question

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

Answer 1

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

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)

Answer 2

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

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

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

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

Answer 3

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

getAllPossibleSums(list)
    if(list.length == 1)
        return list[0];
    otherSums = getAllPossibleSums(list[1:end])
    return union(
        otherSums, list[0] + otherSums);

Answer 4

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

Answer 5

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

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

Answer 6

有史以来最简单的方法：

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

希望这会帮助你。