【算法与数据结构】77、LeetCode组合

组合"/>

【算法与数据结构】77、LeetCode组合

文章目录

• 一、题目
• 二、解法
• 三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：如果k是固定的，最直接的方法就是建立k个for循环，将结果全部压入result容器中。很可惜，k不固定，因此暴力解法写不出来。这道题应该用递归+回溯算法来求解，程序当中的backtracking是主要递归函数，利用一个for循环遍历，依次将遍历的数压入path这个临时容器当中，当path的大小=k说明已经找到一个组合，则将path加入result当中，然后将刚加入的数弹出（例如path=[1 2]， 已经加入Result，将2弹出，然后path当中会压入3, 变成[1 3]），如此循环，结束时得到所有的组合。

  进一步做剪枝优化，改变循环的终止条件：

i <= n

i <= n - (k - path.size()) + 1

  程序如下：

class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> 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:vector<vector<int>> 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:vector<vector<int>> result;     // 结果合集vector<int> 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:vector<vector<int>> combine(int n, int k) {backtracking(n, k, 1);return result;}
};int main() {int n = 4, k = 2;Solution s1;vector<vector<int>> result = s1bine(n, k);for (vector<vector<int>>:: iterator it = result.begin(); it != result.end(); it++) {for (vector<int>::iterator jt = (*it).begin(); jt != (*it).end(); jt++) {cout << *jt << " ";}cout << endl;}system("pause");return 0;
}

end