theme: channing-cyan
Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。
一、题目描述：
给定两个整数 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） 链接：https://leetcode-cn.com/problems/combinations
二、思路分析：
本题这是回溯法的经典题目。直接的解法当然是使用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);
}
}四、总结：
回溯法和递归一样，开始学习的时候会觉得有些绕，所以一定要多加练习，逐渐体会回溯的过程，理清代码的组成结构，一定会有所进步！
掘友们，解题不易，留下个赞或评论再走吧！谢啦~ 💐
