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);
}
}
四、总结:
回溯法和递归一样,开始学习的时候会觉得有些绕,所以一定要多加练习,逐渐体会回溯的过程,理清代码的组成结构,一定会有所进步!
掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐