Find all subsets of an int array whose sums equal a given target

I am trying to implement a function below:


Given a target sum, populate all subsets, whose sum is equal to the target sum, from an int array.

For example:

Target sum is 15.

An int array is { 1, 3, 4, 5, 6, 15 }.

Then all satisfied subsets whose sum is 15 are as follows:

15 = 1+3+5+6
15 = 4+5+6
15 = 15

I am using java.util.Stack class to implement this function, along with recursion.

GetAllSubsetByStack class

import java.util.Stack;

public class GetAllSubsetByStack {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 15;

    private Stack stack = new Stack();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;

    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex  stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }
}

Main class

public class Main {

    private static final int[] DATA = { 1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 13,
        14, 15 };

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}

Output in Console is as follows:

```
15 = 1+3+4+5+2
15 = 1+3+4+7
15 = 1+3+5+6
15 = 1+3+2+9
15 = 1+3+11
15 = 1+4+2+8
15 = 1+4+10
15 = 1+5+2+7
15 = 1+5+9
15 = 1+6+8
15 = 1+14
15 = 3+4+6+2
15 = 3+4+8
15 = 3+5+7
15 = 3+2+10
15 = 4+5+6
15 = 4+2+9
15 = 4+11
15 = 5+2+8
15 = 5+10
15 = 6+2+7
15

There are three reasonable responses here:

• yes, your recursion code can be improved for performance.

• yes, part of that improvement can come from sorting the data.

• yes, there's a way to refactor the code to not use recursion, and it may even be faster.

Bearing that in mind, this answer becomes 'complicated'.

Basic performance improvements for current code:

if (sumInStack == TARGET_SUM) {
    print(stack);
}

can easily be:

if (sumInStack >= TARGET_SUM) {
    if (sumInStack == TARGET_SUM) {
        print(stack);
    }
    // there is no need to continue when we have an answer
    // because nothing we add from here on in will make it
    // add to anything less than what we have...
    return;
}

I dislike any recursive function which rely on external (outside-the-method) values. In your case, the sumInStack is external. This makes the target hard to 'see'.

Additionally, if we do sort the data, there are some benefits we can have, and a way to restructure the recursion to make it do less work (since we can guarantee that all values after a point have certain properties...):

consider the method (assuming sorted data):

public void populateSubset(final int[] data, int fromIndex, 
                           final int[] stack, final int stacklen,
                           final int target) {
    if (target == 0) {
        // exact match of our target. Success!
        printResult(Arrays.copyOf(stack, stacklen));
        return;
    }

    while (fromIndex  target) {
        // take advantage of sorted data.
        // we can skip all values that are too large.
        fromIndex++;
    }

    while (fromIndex < data.length && data[fromIndex] <= target) {
        // stop looping when we run out of data, or when we overflow our target.
        stack[stacklen] = data[fromIndex];
        populateSubset(data, fromIndex + 1, stack, stacklen + 1, target - data[fromIndex]);
        fromIndex++;
    }
}

You would call this function with:

Arrays.sort(data); 
populateSubSet(data, 0, new int[data.length], 0, 15);

So, that is 'can the code be improved?' and 'will sorting help'

As for the 'unrolled' (no recursion) version of the system, it can be done. It would require three int[] arrays:

int[] data = {....}
int[] sum = new int[data.length];
int[] indices = new int[data.length];
int depth = 0;
int lastindex = -1;

The sum gives and indices act like a stack, and the depth is how deep the stack is (again, assume sorted data):

Arrays.sort(data);
while (depth >= 0) {
    lastindex++;
    if (lastindex == data.length) {
        // we have run out of data.
        do {
            // walk up the stack till we find some data.
            depth--;
        while (depth >= 0 && (lastindex = indices[depth] + 1) = 0) {
         .....
         you then add your code in here to check the target,
         keep it updated in your 'stack'.
         go down a level and move on....
    }

}

StackExchange Code Review Q#36214, answer score: 18