77. 组合（回溯算法）

77. 组合

• 题目
• 解题思路
• 代码

题目

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

解题思路

来理解一下题目：输入 n = 4, k = 2，输出如下结果，

顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复），所以要用一个start变量来控制不出现重复的组合。
然后画出决策树，套用模板即可。

代码

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n <= 0) return res;
        LinkedList<Integer> track = new LinkedList<>();

        //注意这里的start初始值为1，就是为了去掉[]这个子树，直接从“1开头的子树”开始
        backtrack(n, k, track, 1);
        return res;
    }

    public void backtrack(int n, int k, LinkedList<Integer> track, int start) {
        //截止条件：track中需要存放和k长度相同的子树
        if(k==track.size()){
            res.add(new LinkedList(track));
            return;
        }
        //需要一个start来防止子集重复，即实现以“某个数开头的子集”
        for (int i = start; i <=n; i++) {
            track.add(i);
            //进入下一层决策树
            backtrack(n, k,track, i + 1);
            track.removeLast();
        }
    }
}