LeetCode216 组合总和 III

本文主要是介绍LeetCode216 组合总和 III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

题目： 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)$

这篇关于LeetCode216 组合总和 III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---