Given an array of integers and number num.

I need to write a function public static int printExpr(int[] a, int num)

The function should print all the combinations that can give the number num with or - operators, and to return the number of combinations.

The solution should be recursive

For example, for the given array:

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

The output should be:

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

5

My attempt:

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

My output:

 1 3=4
 1-3 6=4

2

I think that this question is kind of SubsetSum.

What am I missing?

Note LinkedList, HashSet, etc. are not allowed.

CodePudding user response：

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

CodePudding user response：

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