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

Question

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<Integer> stack = new Stack<Integer>();

    /** 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 < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                sumInStack -= (Integer) stack.pop();
            }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> 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 = 6+9
15 = 2+13
15 = 7+8
15 = 15

Please help me with the following 2 things:

1. How can I improve this code to reduce the times for recursion? Is sorting the int array (from high to low) before recursion a better way?

2. Is there a way to improve the code without using recursion?

Answer 1

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 < data.length && data[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) < data.length);
    }
    if (depth >= 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....
    }

}

Answer 2

Another way to do problems like this — investigating properties of all subsets (that is, members of the "power set") — is to think of the main set as a list of cells, and each cell as a binary digit position. A member of the power set can therefore be described by a binary number, such that the subset contains only those elements of the set corresponding to a 1 in the binary value.

By doing that, you can generate the power set just by counting. Of course this gets a little complicated when the original set has more values in it that can be comfortably dealt with by the native integer type in a given programming language, but Java has BigInteger. (Enumerating a power set for any purpose is going to be a little painful for original sets that big anyway.)

Answer 3

I have not fully worked it out, but the best algorithm here is probably dynamic programming. Basically, I would order the values and at each one keep all possible sums, considering earlier sums.

For example, for input {1, 2, 3, 4, 6}:

Value : possible sums considering earlier sums and current value
1     : 0, 1
2     : 0, 1, 2, 3     (that is: 1 + 0 * 2, 0 * 1 + 2, 1 + 2)
3     : 0, 1, 2, 3, 4, 5, 6
4     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11
6     : 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8, 12, 13, 15, 16

Note that there is some efficiency above because some combinations are repeated many times. For example, at item 3, the output value 3 can be obtained from either (1 * 3_from_previous_sum + 0 * 3) or (0 * 3_from_previous_sum + 1 * 3). The further you go, the more such redundant values happen.

I have not worked out is if this would clearly be more efficient than using brute force search, but I am pretty sure it would. Dynamic programming should increase the memory requirement of the algorithm, but decrease the compute time.

The example table I made would be useful to answer whether a given sum can be attained or not, but not to give all combinations that can produce a sum, if it exists. To answer that second question, the table would have to be modified to also associate with each output sum value all the combinations which can produce it.