Return Path at the root node when using recursion

Question

I am trying to create a recursive function for subset-sum problem. I have created a function inspired by this answer.

Problem: I am trying to pick some elements from array some array (e.g. [50,40,30,20]) whose sum is given my some value defined as sum (e.g. 100).

I have created slightly modified function as suggested in that answer.

Picking up from the front and selected it or not selecting it.

If I select an element, the sum from the reduced list will be less than the element selected, else if I do not select that element, the sum from the reduced list will be the original one.

But, what I am finding the most difficult thing is returning the path traced to the root node of the recursive calls. I am able to print the path when I reached the node where sum is matched.

Here is my function:

private static boolean findSumFromSubList(ArrayList<Integer> set, Integer sum, ArrayList<Integer> result) {

    if (sum < 0)
        return false;

    if (sum == 0) {
        // Got it! Awesome! Print it!
        System.out.println(result);
        return true;
    }

    if (set.size() == 0 && sum != 0)
        return false;

    ArrayList<Integer> newSet = new ArrayList<>(set);
    newSet.remove(0);

    System.out.println("Left: Picking up " + set.get(0));
    result.add(set.get(0));
    if (findSumFromSubList(newSet, sum - set.get(0), new ArrayList<>(result))) {
        return true;
    }

    System.out.println("Right: NOT Picking up " + set.get(0));
    result.remove(result.size()-1);
    if (findSumFromSubList(newSet, sum, new ArrayList<>(result))) {
        return true;
    }

    return false;
}

I am calling it this way:

    ArrayList<Integer> pair = new ArrayList<>();
    pair.add(50);
    pair.add(40);
    pair.add(30);
    pair.add(20);
    ArrayList<Integer> result = new ArrayList<>();
    boolean resultBool = findSumFromSubList(pair, 100, result);

    System.out.println("bool: " + resultBool + ", result: " + result);

The output I am getting is:

Left: Picking up 50
Left: Picking up 40
Left: Picking up 30
Right: NOT Picking up 30
Left: Picking up 20
Right: NOT Picking up 20
Right: NOT Picking up 40
Left: Picking up 30
Left: Picking up 20
[50, 30, 20]
bool: true, result: [50]

So I am able to get the output inside the recursion, but how can I return that value to the root calling function. Because result returns 50 only.

Answer 1

Instead of copying result, try passing it along so it can be modified as it recurses.

private static boolean getSum(ArrayList<Integer> set, Integer sum, LinkedList<Integer> result) {
    // ...

    System.out.println("Left: Picking up " + set.get(0));
    result.add(set.get(0));
    if (getSum(newSet, sum - set.get(0), result)) {
        return true;
    }
    result.removeLast();

    System.out.println("Right: NOT Picking up " + set.get(0));
    if (getSum(newSet, sum, result)) {
        return true;
    }
}

You can apply similar logic to set, but I'll leave that as an exercise to the reader.