# 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<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


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?

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) {
.....
keep it updated in your 'stack'.
go down a level and move on....
}

}

• I can think of so many awesome things to do with memoization! We can store all the solutions in ArrayList<ArrayList<Integer>> for a particular (fromIndex, target) pair – Vikrant Goel Jun 3 '15 at 8:22

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.)

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.