代码随想录算法训练营第二十四天

LeetCode 77.组合

backtracking专题第一题，一开始对递归出口的处理没有特别好，一开始使k在递归过程中随着递归的深入不断减少遇到了一些问题，有点麻烦，直接使用k == path.size 判断就好了。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> path = new LinkedList<>();
        myCombine(ans, path, n, k, 1);
        return ans;
    }

    // for instance, n = 20, K = 3,
    // the tartet ans is the combination of every 2 elements in [1, 20]
    private void myCombine (List<List<Integer>> ans, List<Integer> path, int n, int k, int index) { 
        
        // recursion exits
        if (path.size() == k) {
            List<Integer> combine = new LinkedList<>();
            combine.addAll(path);
            ans.add(combine);
            return;
        }
        
        // this is to remove those unvalid recursion
        for (int i = index; i <= n - (k - path.size()) + 1 ; i++) {
            path.add(i);
            myCombine(ans, path, n, k, i + 1);
            path.remove(path.get(path.size() - 1));

        }
 
    }

}