Skip to content

Instantly share code, notes, and snippets.

@fzakaria
Created April 23, 2015 00:53
Show Gist options
  • Save fzakaria/50943139c85557192ac5 to your computer and use it in GitHub Desktop.
Save fzakaria/50943139c85557192ac5 to your computer and use it in GitHub Desktop.
SubsetSum
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment