前言

题目： 216. 组合总和 III
文档： 代码随想录——组合总和 III
编程语言： C++
解题状态： 成功解答

思路

组合题的变种，其实是变得更简单了，还是可以使用回溯法来解决。

代码

回溯法

class Solution {
private:vector<vector<int>> res;vector<int> path;void backtracking(int k, int n, int startIndex) {if (path.size() == k) {int sum = 0;for (int i = 0; i < k; i++) {sum += path[i];}if (sum == n) {res.push_back(path);}return;}for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {path.push_back(i);backtracking(k, n, i + 1);path.pop_back();}}
public:vector<vector<int>> combinationSum3(int k, int n) {res.clear();path.clear();backtracking(k, n, 1);return res;}
};

• 空间复杂度： $O(n)$