Skip to content

Instantly share code, notes, and snippets.

@gabhi
Created June 10, 2014 06:18
Show Gist options
  • Save gabhi/a21e9594330f52b3039f to your computer and use it in GitHub Desktop.
Save gabhi/a21e9594330f52b3039f to your computer and use it in GitHub Desktop.
Find all subsets of length k in an array
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
//successful stop clause
if (current.size() == k) {
solution.add(new HashSet<>(current));
return;
}
//unseccessful stop clause
if (idx == superSet.size()) return;
Integer x = superSet.get(idx);
current.add(x);
//"guess" x is in the subset
getSubsets(superSet, k, idx+1, current, solution);
current.remove(x);
//"guess" x is not in the subset
getSubsets(superSet, k, idx+1, current, solution);
}
public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
List<Set<Integer>> res = new ArrayList<>();
getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
return res;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment