20天刷题计划-77. 组合

一、题目描述：

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

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 示例 2：

输入：n = 1, k = 1 输出：[[1]]

提示：

1 <= n <= 20 1 <= k <= n

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/co…

二、思路分析：

本题这是回溯法的经典题目。直接的解法当然是使用for循环，思路简单但效率相对没有优势，可以使用回溯搜索法，具体步骤如下

定义成全局变量便不必再当作参数传入函数

剪枝，判断当前长度和数组剩余长度能否构成一个k个数的组合

for 循环里 i 从 start 到 n。

比如，n = 5，k = 4，temp.size( ) == 1，此时代表我们还需要（4 - 1 = 3）个数字，

如果 i = 4 的话，以后最多把 4 和 5 加入到 temp 中，而此时 temp.size() 才等于 1 + 2 = 3，

不够 4 个，所以 i 没必要等于 4，i 循环到 3 就足够了。

所以 for 循环的结束条件可以改成， i <= n - ( k - temp.size ( ) ) + 1，因为我们最后取到了 n，所以还要加 1。

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    getAns(1,n, k, new ArrayList<Integer>(), ans);
    return ans;
}
​
private void getAns(int start, int n, int k, ArrayList<Integer> temp, List<List<Integer>> ans) { 
    if(temp.size() == k){
        ans.add(new ArrayList<Integer>(temp));
        return;
    }
    for (int i = start; i <= n - (k -temp.size()) + 1; i++) {
        temp.add(i);
        getAns(i+1, n, k, temp, ans);
        temp.remove(temp.size() - 1);
    }
}

四、总结：

回溯法和递归一样，开始学习的时候会觉得有些绕，所以一定要多加练习，逐渐体会回溯的过程，理清代码的组成结构，一定会有所进步！

掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐