【算法与数据结构】216、LeetCode组合总和 III

组合总和 III"/>

【算法与数据结构】216、LeetCode组合总和 III

文章目录

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

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

一、题目

二、解法

  思路分析：本题可以直接利用77题的代码【算法与数据结构】77、LeetCode组合，稍作修改即可使用。
  程序如下：

class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(int n, int k, int startIndex) {if (path.size() == k) {if(accumulate(path.begin(), path.end(), 0) == n)    result.push_back(path);               return;}for (int i = startIndex; i <= n; 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)。
    考虑到代码的效率，进一步修改代码，做剪枝优化：

class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(int n, int k, int sum, int startIndex) {if (sum > n) return;    // 剪枝if (path.size() == k) {           if(sum == n)    result.push_back(path);               return;}for (int i = startIndex; i <= 9 -(k - path.size()) + 1; i++) {sum += i;path.push_back(i);  // 处理节点backtracking(n, k, sum, i + 1);  // 递归sum -= i;   // 回溯path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum3(int k, int n) {backtracking(n, k, 0, 1);return result;}
};

三、完整代码

# include <iostream>
# include <vector>
using namespace std;class Solution {
private:vector<vector<int>> result;     // 结果合集vector<int> path;void backtracking(int n, int k, int sum, int startIndex) {if (sum > n) return;    // 剪枝if (path.size() == k) {           if(sum == n)    result.push_back(path);               return;}for (int i = startIndex; i <= 9 -(k - path.size()) + 1; i++) {sum += i;path.push_back(i);  // 处理节点backtracking(n, k, sum, i + 1);  // 递归sum -= i;   // 回溯path.pop_back();    // 回溯，撤销处理的节点}}
public:vector<vector<int>> combinationSum3(int k, int n) {backtracking(n, k, 0, 1);return result;}
};int main() {int n = 7, k = 3;Solution s1;vector<vector<int>> result = s1binationSum3(k, n);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