打印所有可以用`＆＃x2b;'或` - ` - 运算符的组合

Question

给定 Array Integers 和数字 num 。

我需要写一个函数 public static int printExpr（int [] a，int num）

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

解决方案应为递归

，例如，给定数组：

{1，3，6，2} and 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

首先，快速回顾 递归 。

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

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

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

在 递归案例 中，有树的替代性分支：

• 我们可以忽略它；
• 贡献目标 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

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