使用 `+` 或 `-` 运算符打印可以给出给定数字的所有组合

Question

给定数组的整数和数字 num.

我需要写一个函数public static int printExpr(int[] a, int num)

该函数应该打印所有组合可以用 + 或 - 运算符给出数字 num，并 return 组合的数量.

解决方案应该是递归

例如，对于给定的数组：

{1, 3, 6, 2} 和 num=4

输出应该是：

+3+1=4
+6-3+1=4
+2+3-1=4
+2+6-3-1=4
-2+6=4

5

我的尝试：

    public static void main(String[] args) {
        int[] a = {1, 3, 6, 2};
        System.out.println("\n" + printExpr(a, 4));
    }

    public static int printExpr(int[] a, int num) {
        return printExpr(a, num, 0, 0, "");
    }

    public static int printExpr(int[] a, int num, int i, int sum, String s) {
        if (i < 0 || i >= a.length)
            return 0;
        if (num == sum) {
            System.out.println(s+"=4");
            return 1 +  printExpr(a, num, i , 0,  "") ;

        }
        return printExpr(a, num, i + 1, sum, s + "")+printExpr(a, num, i + 1, sum + a[i], s + "+" + a[i]) + printExpr(a, num, i + 1, sum - a[i], s + "-" + a[i]) ;
    }

我的输出：

+1+3=4
+1-3+6=4

2

我觉得这个问题有点SubsetSum。

我错过了什么？

注意 LinkedList, HashSet,等等都是不允许的.

Answer 1

首先，快速回顾一下递归。

每个递归实现都由两部分组成：

Base case - 代表一组简单 edge-cases 的部分应该终止递归。这些 edge-cases 的结果是预先知道的。对于此任务，第一个 base case 是达到目标总和并且 expression 必须打印在控制台上并且 return 值 必须是 1（即找到一个组合）。另一种 base case 是 array 被完全发现但当前总和与目标不同的情况。对于这种情况，return 值将是 0.
递归案例 - 方法中进行递归调用和主要逻辑所在的部分。

递归情况:

我们可以忽略它；
贡献目标sum（加到当前字符串前加上+符号，目标减去sum）；
或从 sum 中减去它（添加到当前字符串前加上 - 符号并将其添加到目标 sum）。

在所有这些情况下，我们需要在递归调用方法时将索引推进1。

为了找到组合的总数，我们需要引入一个变量（在下面的代码中表示为count).每个 递归分支 的结果 return 将贡献该变量。

代码可能如下所示：

public static int printExpression(int[] arr, int sum) {
    return printExpression(arr, 0, "", sum);
}

public static int printExpression(int[] arr, int current, String expression, int sum) {
    if (sum == 0) { // base case - target sum has been reached
        System.out.println(expression);
        return 1;
    }
    if (current == arr.length) {  // base case - target sum wasn't reached and current index is out of bounds
        return 0;
    }
    // recursive case
    int count = 0;
    count += printExpression(arr, current + 1, expression, sum); // ignore current element
    count += printExpression(arr, current + 1, expression + "+" + arr[current], sum - arr[current]); // add current element (i.e. subtract from the target sum)
    count += printExpression(arr, current + 1, expression + "-" + arr[current], sum + arr[current]); // subtract current element (i.e. increase the target sum)
    return count;
}

public static void main(String[] args) {
    int combinationCount = printExpression(new int[]{1, 3, 6, 2}, 4);
    System.out.println("Number of combinations: " + combinationCount);
}

输出

+6-2
+1+3
+1-3+6
-1+3+2
-1-3+6+2
Number of combinations: 5

Answer 2

public static int printExpr(int[] a, int num) {
        return printExpr(a, num, 0, 0, "");
    }

    public static int printExpr(int[] a, int num, int i, int sum, String s) {
        if (i < 0 || i >= a.length){
            if (num == sum) {
                System.out.println(s + "=4");
                return 1;
            }
            return 0;
        }

        if (num == sum) {
            System.out.println(s+"=4");
            return 1;
        }

        return printExpr(a, num, i + 1, sum, s)+printExpr(a, num, i + 1, sum + a[i], s + "+" + a[i]) + printExpr(a, num, i + 1, sum - a[i], s + "-" + a[i]) ;
    }

输出：

+6-2=4
+1+3=4
+1-3+6=4
-1+3+2=4
-1-3+6+2=4

5

使用 `+` 或 `-` 运算符打印可以给出给定数字的所有组合

Print all the Combinations that can give the given Number with `+` or `-` operators

java

arrays

algorithm

recursion

combinations