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+615 = 4+5+615 = 15I am using java.util.Stack class to implement this function, along with recursion.GetAllSubsetByStack classimport 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 classpublic 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+215 = 1+3+4+715 = 1+3+5+615 = 1+3+2+915 = 1+3+1115 = 1+4+2+815 = 1+4+1015 = 1+5+2+715 = 1+5+915 = 1+6+815 = 1+1415 = 3+4+6+215 = 3+4+815 = 3+5+715 = 3+2+1015 = 4+5+615 = 4+2+915 = 4+1115 = 5+2+815 = 5+1015 = 6+2+715 = 6+915 = 2+1315 = 7+815 = 15Please help me with the following 2 things: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?Is there a way to improve the code without using recursion?
Find all subsets of an int array whose sums equal a given target
java;array;recursion;mathematics;combinatorics
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....    }}