28
\$\begingroup\$

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?

\$\endgroup\$
18
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Vikrant Goel Jun 3 '15 at 8:22
-1
\$\begingroup\$

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

\$\endgroup\$
-1
\$\begingroup\$

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.

\$\endgroup\$

protected by Community Apr 9 '15 at 18:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.