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

Question

给定一个包含整数和数字num的数组。

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

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

解决方案应该是递归

例如，对于给定的数组:

{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

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

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

• 基本情况 - 代表一组应该终止递归的简单边缘情况的部分。这些边缘案例的结果是预先知道的。对于此任务，第一个基本情况是达到目标总和并且必须在控制台上打印表达式并且return value 必须是 1(即找到一个组合)。另一种基本情况 是数组 已被完全发现但当前总和与目标不同的情况。对于这种情况，返回值将为 0。

• Recursive case - 进行递归调用和主要逻辑所在的方法部分。

在递归情况中有树状的分支执行:

• 我们可以忽略它；
• 贡献目标sum(加到当前字符串前面有+符号，减去目标sum)；
• 或者从sum中减去它(加到当前字符串前面加上-符号加到目标sum ).

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

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

代码可能是这样的:

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