_{菜鸡学习记录}

题目链接：77. 组合 - 力扣（LeetCode） (leetcode-cn.com)

这道题目我一看就觉得该用回溯，然后就开始回溯了，结果磕磕碰碰写了40分钟才写完。

思路

首先这道题目没想太多，就是为了控制不重复加入相同元素，添加了一个变量start，表示遍历的起始位置。

预想是这样的，加入了第一个元素之后（假设这个元素的下标为index），后面的元素就要从index+1的位置开始遍历。

然后为了不重复，从小到大枚举填入第一个数字，但是这个第一个数字并不是[1,n]内的都能填入，比如n=4,k=1时，可以填入第一个位置的最大数字是4，当n=4,k=2，可以填入第一个位置的最大数字是3……

所以可以得到可填入第一个位置的最大数字maxStart为n+1-k。

只要保证填入的第一个数字范围在[1,n+1-k]，而后面的数字逐个遍历填入即可。

代码

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    dfs(result, temp, n, k, 0, 1);
    return result;
}

public void dfs(List<List<Integer>> res, List<Integer> temp, int n, int k, int count, int start) {
    if (count == k) {
        res.add(new ArrayList<>(temp));
        return;
    }

    for (int i = start; i <= n; i++) {
        if (start > n + 1 - k && temp.size() == 0) {
            break;
        }
        temp.add(i);
        dfs(res, temp, n, k, count + 1, i + 1);//start+1表示不重复添加元素
        temp.remove(temp.size() - 1);//移除加入的最后一个
    }
}

总结

可能看起来还蛮复杂的，但是我每次做回溯都差不多是类似的思路，还是要多做才能掌握框架。