博客

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

输入：n = 4, k = 2

输出：

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

标签：回溯、递归

回溯算法相当于在树中取值

以n = 4 ;k = 3为例

/**
*思路：通过递归使用回溯法；
*考虑要素：递归边界、递归深度，每一层的递归宽度
*/
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combineHelper(n, k, 1);
        return result;
    }

    private void combineHelper(int n, int k, int startIndex){
        //终止条件，即递归边界
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        //循环就是取这个节点中的所有值，i代表节点中的值，start代表起点
        /*n - (k - path.size())+1 当层的这个节点的最大值，比如第
        *二层的所有节点，能放的最大值为3，不能为4（为4的话第三层就没得放）
        */
        for (int i = start; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            //递归代表进入了下一层
            combineHelper(n, k, i + 1);
            path.removeLast();
        }
    }
}