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

Firstly, a quick recap on recursion.

Every recursive implementation consists of two parts:

• Base case - a part that represents a set of simple edge-cases which should terminate the recursion. The outcome for these edge-cases is known in advance. For this task, the first base case is when the target sum is reached and the expression has to be printed on the console and the return value has to be 1 (i.e. one combination was found). Another base case is a situation when array was fully discovered but the current sum differs from the target. For this case, return value will be 0.

• Recursive case - the part of the method where recursive calls are made and where the main logic resides.

There are tree alternative branches of execution in the recursive case:

• we can either ignore it;
• contribute the target sum (add to the current string with + sign in front of it and subtract it from the target sum);
• or subtract it from the sum (add to the current string with - sign in front of it and add it to the target sum).

In all these cases, we need to advance the index by 1 while calling the method recursively.

In order to found the total number of combinations, we need to introduce a variable (denoted as count in the code below). And the result returned by every recursive branch will contribute that variable.

The code might look like this:

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

Output

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

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

Output:

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

5