弘泽建设集团网站,已有域名 做网站,网页设计需要什么专业,泸州市建设厅网站77.组合
77. 组合 - 力扣#xff08;LeetCode#xff09;
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 示例 1#xff1a;
输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,2],[1,3…77.组合
77. 组合 - 力扣LeetCode
给定两个整数 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 201 k n
思路
若是使用for循环嵌套组合1到n中的数若k取大一点就会有非常多的嵌套for要写明显是不合适的所以这里引入了回溯的思想直观的想法是画出递归树这里引用了力扣大佬画的图 这里我们需要使用一个表示路径的栈path去记录已选择的数。
class Solution {public ListListInteger combine(int n, int k) {ListListInteger resnew ArrayList();//答案if(k0||nk){return res;}DequeInteger pathnew ArrayDeque();dfs(n,k,1,path,res);//题目要求从1开始return res;}private void dfs(int n,int k,int begin,DequeInteger path,ListListInteger res){if(path.size()k){//如果path长度已经要寻找的数个数说明找到一组答案res.add(new ArrayList(path));return;}for(int ibegin;in-(k-path.size())1;i){//此处是一个优化思想如果n7k4那么从5开始搜索已经没有意义了所以搜索起点有上界。path.addLast(i);//将当前节点记录进pathdfs(n,k,i1,path,res);//将path传入下一次递归从i1开始寻找path.removeLast();//将该节点删除代表了回溯的操作。}}}
思路2.按照每一个数选与不选递归。
public class Solution {public ListListInteger combine(int n, int k) {ListListInteger res new ArrayList();if (k 0 || n k) {return res;}// 为了防止底层动态数组扩容初始化的时候传入最大长度DequeInteger path new ArrayDeque(k);dfs(1, n, k, path, res);return res;}private void dfs(int begin, int n, int k, DequeInteger path, ListListInteger res) {if (k 0) {res.add(new ArrayList(path));return;}if (begin n - k 1) {return;}// 不选当前考虑的数 begin直接递归到下一层dfs(begin 1, n, k, path, res);// 不选当前考虑的数 begin递归到下一层的时候 k - 1这里 k 表示还需要选多少个数path.addLast(begin);dfs(begin 1, n, k - 1, path, res);// 深度优先遍历有回头的过程因此需要撤销选择path.removeLast();}
}
总结
回溯法第一题卡了好几天需要加强复习。
