// @Title: 组合 (Combinations)
// @Author: qisiii
// @Date: 2024-09-19 00:29:50
// @Runtime: 22 ms
// @Memory: 92.3 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), k, 1, n);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int k, int num, int n) {
        //终止条件1：当list个数达到k时
        if (list.size() == k) {
            result.add(new ArrayList<>(list));
            return;
        }
        //终止条件2: 超出范围n时
        if (num > n) {
            return;
        }
        //选择当前数
        list.add(num);
        dfs(result, list, k, num + 1, n);
        //不选当前数
        list.remove(list.size() - 1);
        dfs(result, list, k, num + 1, n);
    }
}