class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
int[] number = new int[n];
for (int i = 0; i < n; i++) {
number[i] = i + 1;
}
helper(n, k, 0, number, cur, res);
return res;
}
private void helper(int n, int k, int index, int[] number, List<Integer> cur, List<List<Integer>> res) {
if (cur.size() > k) {
return;
}
if (cur.size() == k) {
res.add(new ArrayList<>(cur));
return;
}
for (int i = index; i < n; i++) {
cur.add(number[i]);
helper(n, k, i + 1, number, cur, res);
cur.remove(cur.size() - 1);
}
}
}