Pass values from inner recursive methods to outer methods

Question

I found the following method from http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/ which prints all the subsets in an array that sum to a certain number.

My code is full of print statements which I used to trace the recursive calls:

public static void find(int[] A, int currSum, int index, int sum,
        int[] solution, int tot) {
    if (currSum == sum) {
                    tot +=1;

        System.out.println("\nSum found ");
        for (int i = 0; i < solution.length; i++) {
            if (solution[i] == 1) {
                System.out.print("  " + A[i]);
            }
        }

    } else if (index == A.length) {
                System.out.println("reached end");
        return;
    } else {
        solution[index] = 1;// select the element
        currSum += A[index];
                    System.out.println("incr " + A[index] + "  "+ currSum + " ");
        find(A, currSum, index + 1, sum, solution, tot);
        currSum -= A[index];
                    System.out.println("decr " + A[index] + "  "+ currSum + " ");
        solution[index] = 0;// do not select the element
        find(A, currSum, index + 1, sum, solution, tot);
    }
    return;            
}

I want to modify the method so that it also prints the final number of solutions in the end. I know this question has been discussed on Stackoverflow and I found some interesting solutions. Nevertheless, I want to find out whether there is a way to modify this particular method. My idea was to create an integer "tot" to which I add 1 as soon as I find a solution and then pass the updated value to every recursive call. But the final value will be found in one of the inner recursive calls and I don't know how to pass the final value to the outer methods.

Answer 1

If you want to get a solution count in recursive calls, best way would be to pass a mutable reference in each method call. As soon as you get a solution, update the mutable reference. Here, mutable reference is important because:

1. primitive types would be hard to propagate through recursive calls as return types will need to be maintained and updated accordingly.
2. immutable types (like Integer) will not maintain values across recursive calls.

Solutions:

1. Use AtomicInteger
2. Use primitive int array

Both will be able to solve your problem. You should check for null reference or length of array to make it less error prone. Samples given below:

private static void methodWithAtomicInteger(AtomicInteger i){
    i.incrementAndGet();
}

private static void methodWithIntArray(int[] i){
    i[0]++;
}

public static void main(String[] args){
    AtomicInteger integer = new AtomicInteger(0);
    System.out.println(integer);
    methodWithAtomicInteger(integer);
    System.out.println(integer);

    int[] values = new int[]{0};
    System.out.println(values[0]);
    methodWithIntArray(values);
    System.out.println(values[0]);
}