做任务网站,抚州建设银行网站,酒店的网站建设方案,小程序制作需要审核资质吗文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;如果k是固定的#xff0c;最直接的方法就是建立k个for循环#xff0c;将结果全部压入result容器中。… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析如果k是固定的最直接的方法就是建立k个for循环将结果全部压入result容器中。很可惜k不固定因此暴力解法写不出来。这道题应该用递归回溯算法来求解程序当中的backtracking是主要递归函数利用一个for循环遍历依次将遍历的数压入path这个临时容器当中当path的大小k说明已经找到一个组合则将path加入result当中然后将刚加入的数弹出例如path[1 2] 已经加入Result将2弹出然后path当中会压入3, 变成[1 3]如此循环结束时得到所有的组合。 进一步做剪枝优化改变循环的终止条件
i ni n - (k - path.size()) 1程序如下
class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n - (k - path.size()) 1; i) { // 剪枝优化path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return result;}
};复杂度分析
时间复杂度 O ( n ∗ 2 n ) O(n*2^n) O(n∗2n)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
using namespace std;class Solution {
private:vectorvectorint result; // 结果合集vectorint path;void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n - (k - path.size()) 1; i) { // 剪枝优化path.push_back(i); // 处理节点backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return result;}
};int main() {int n 4, k 2;Solution s1;vectorvectorint result s1.combine(n, k);for (vectorvectorint:: iterator it result.begin(); it ! result.end(); it) {for (vectorint::iterator jt (*it).begin(); jt ! (*it).end(); jt) {cout *jt ;}cout endl;}system(pause);return 0;
}end
