Enumerate all subsets of size k Combinations.java
public static List<List<Integer>> combinations(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> ans = new ArrayList<>();
combinationsHelper(n, k, 0, ans, res);
return res;
}
private static void combinationsHelper(int n, int k, int start,
List<Integer> ans,
List<List<Integer>> res) {
if (ans.size() == k) {
res.add(new ArrayList<>(ans));
return;
}
// not add start+1 element, but only do this when still possible to get k elements from remaining elements
if (k - ans.size() <= n - (start + 1)) {
combinationsHelper(n, k, start + 1, ans, res);
}
ans.add(start + 1);
combinationsHelper(n, k, start + 1, ans, res);
ans.remove(ans.size() - 1);
}
