public class Combinations {
public static void main(String[] args) {
int n = 4;
int k = 2;
List<List<Integer>> ans = combine(n, k);
System.out.println(ans);
}
public static List<List<Integer>> combine(int n, int k) {
List<Integer> track = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
recurse(1, n, k, track, ans);
return ans;
}
private static void recurse(int depth, int n, int k, List<Integer> track, List<List<Integer>> ans) {
if (track.size() == k) {
List<Integer> sol = new ArrayList<>(track);
ans.add(sol);
return;
}
if (depth > n) {
return;
}
track.add(depth);
recurse(depth + 1, n, k, track, ans);
track.remove(track.size() - 1);
recurse(depth + 1, n, k, track, ans);
}
}