网站开发支付宝二维码支付,做网站比较好,科技尽头,百度推广多少钱一天一:题目
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1#xff1a;
输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2#xff1a;输入#xff1a;n …一:题目
给定两个整数 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,2},{2,1} 这两个是等价的
思路 1.经典回溯算法题我们正常来思考这道题的时候 如果 k 2,我们可能会用两层for循环来解决 但如果 k 一直往上增加 那么就要套k层循环 如此的话是不合理的所以要用到递归回溯 2.这里选择的解的空间依然是 排列树 因为逐层往下的分支树木减少 第一层 1 2 3 4 第二层 2 3 4 第三层3 4 第四层 4 3.在这里我们选取for循环来遍历给定的容器里的元素纵向是backstacking()递归寻求结果 到达叶 节点 这里也就是递归结束的时候将结果存在另一个容器当中。 4.具体写码 1:递归函数的返回值和参数 返回值:vectorvector res :用来存最后的结果 vector path 用来存每次的求取的结果 backtracking(n,k,index):这里的 n 和 k就是题目中给出的参数 需要注意的是 这里的 index 是需要记录我们每次的都是在不断缩小范围的
2:回溯终止条件
当path.size() k的时候这时容器中的元素已经装满了这是就是递归终止的条件
3:单层的搜索过层 即 for循环来遍历给定的容器里的元素纵向是backstacking()递归寻求结果 到达叶 节点
三上码未剪枝优化的
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(int n,int k,int index){if(path.size() k){res.push_back(path);return;}for(int i index; i n ; i){path.push_back(i);backtracking(n,k,i1);//每次往下递归的时候使不断缩小范围的path.pop_back();//这里是处理每次递归到叶节点是时候 这时已经处理好一种可行解那么就要为下一种// 可行解提供空间}}vectorvectorint combine(int n, int k) {/**思路1.经典回溯算法题我们正常来思考这道题的时候 如果 k 2,我们可能会用两层for循环来解决但如果 k 一直往上增加 那么就要套k层循环 如此的话是不合理的所以要用到递归回溯2.这里选择的解的空间依然是 排列树 因为逐层往下的分支树木减少 第一层 1 2 3 4 第二层 2 3 4第三层3 4第四层 43.在这里我们选取for循环来遍历给定的容器里的元素纵向是backstacking()递归寻求结果 到达叶节点 这里也就是递归结束的时候将结果存在另一个容器当中。4.具体写码1:递归函数的返回值和参数返回值:vectorvectorint res :用来存最后的结果vectorint path 用来存每次的求取的结果 backtracking(n,k,index):这里的 n 和 k就是题目中给出的参数需要注意的是 这里的 index 是需要记录我们每次的都是在不断缩小范围的 2:回溯终止条件 当path.size() k的时候这时容器中的元素已经装满了这是就是递归终止的条件3:单层的搜索过层 即 for循环来遍历给定的容器里的元素纵向是backstacking()递归寻求结果 到达叶节点 */backtracking(n,k,1);return res;}
};四剪枝
在这里我们考虑的是当 n k的时候 只需要for循环的第一层就足够了 因为再往下就都不符合条件因为 剩下的元素个数已经不够 k个了 这里我们需要在 backtacking()中的for循环做如下更改
for(int i index; i n - (k - path.size()) 1; i) 这里建议举个例子理解 n - (k - path.size()) 1;
比如 n 4,k 3,那么刚开始的时候 path.size() 0, 那么接下来的话 4 - 3 - 0 1 2 我们可以得知即可以的for循环也就两次 i 是从1开始的 123和234
