公司网站注销,深圳seo关键词优化外包公司,江西赣州网络公司,广西网红排名前20名77. 组合 - 力扣#xff08;LeetCode#xff09;
题目描述
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 样例输入
示例 1#xff1a; 输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],…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
题解
暴力算法
int n 4;
for (int i 1; i n; i) {for (int j i 1; j n; j) {cout i j endl;}
}
在上述暴力算法中题目中k等于多少我们就要嵌套多少个for循环显然这样写代码是不合理的而在回溯算法中我们用递归代替嵌套的for循环 回溯算法 核心 for循环的本质是遍历每一层递归的本质是遍历每个深度下的树枝 核心代码 //横向遍历for(int istartIndex;in;i){path.emplace_back(i);//处理节点backing(n,k,i1,path,res);//纵向遍历path.pop_back();//回溯}
在上述代码中我们用for循环用来横向遍历递归的过程是纵向遍历。同时用startIndex控制每层遍历的起始位置每往深层下降一层就用path保存取到的节点i当满足终止条件return返回到上一层前要进行回溯撤销处理的结点。 也就是说backing递归函数通过不断调用自己一直往深处遍历总会遇到叶子节点遇到了叶子节点就要返回。 那么终止条件是什么呢很显然每当我们收集path的过程中path的大小等于k的时候就说明我们已经收集到了一个满足题意的结果此时即可终止本次递归返回上一层即 //递归出口if(path.size()k){res.push_back(path);//收集结果return;} 代码
class Solution {
public:void backing(int n,int k,int startIndex,vectorint path,vectorvectorint res){//递归出口if(path.size()k){res.push_back(path);//收集结果return;}//横向遍历n-(k-path.size())1为剪枝优化for(int istartIndex;in-(k-path.size())1;i){path.emplace_back(i);backing(n,k,i1,path,res);//纵向遍历path.pop_back();//回溯}}vectorvectorint combine(int n, int k) {vectorint path;vectorvectorint res;backing(n,k,1,path,res);return res;}
};
