SubsetSum

gistfile1.java

public class SubsetSum {


    public static List<List<Integer>> subsetSum( List<Integer> list, int sum) {
        List<List<Integer>> solutions = new ArrayList<List<Integer>>();
        Stack<Integer> solution = new Stack<Integer>();
        subsetSum(list, sum,0, solutions, solution);
        return solutions;
    }

    private static void subsetSum(List<Integer> list, int sum, int indx, List<List<Integer>> solutions, Stack<Integer> solution) {
        if (indx >= list.size() ) {
            return;
        }
        Integer curr = list.get(indx);
        if (sum - curr == 0) {
            solution.add(curr);
            solutions.add(new ArrayList<Integer>(solution));
            solution.pop();
            return;
        }

        solution.add(curr);
        subsetSum(list, sum - curr, indx + 1, solutions, solution);
        if (!solution.isEmpty()) {
            solution.pop();
        }

        subsetSum(list, sum, indx+1, solutions, solution);
    }
}