Loading... > https://leetcode.cn/problems/combination-sum-iii/description/?envType=daily-question&envId=2024-04-07 ### 暴力枚举 从 $1-9$ 的正整数中取，且每个数只能取一次。那么每种数字只有两种情况：取或者不取。枚举完所有的情况也只需要 $2^9$ 次，完全是可接受的，因此可以直接暴力枚举： ```c++ class Solution { public: std::vector<std::vector<int>> combinationSum3(int k, int n) { if (n < k * (k - 1) / 2 + k || n > k * (k - 1) / 2 + (10 - k) * k) return {}; std::vector<std::vector<int>> res; std::vector<int> combination; auto check = [&combination, &k, &n] (const int &mask) { combination.clear(); int sum = 0; for (int i = 0; i < 9; ++i) { if (1 << i & mask) { combination.push_back(i + 1); sum += i + 1; } } return combination.size() == k && sum == n; }; for (int mask = 1; mask < 1 << 9; ++mask) { if (check(mask)) res.push_back(combination); } return res; } }; ``` - 时间复杂度 $O(M \times 2^M)$ 。其中 $M$ 为可取数字的范围，本题中固定为 9 。 - 空间复杂度 $O(M)$ 。 ### DFS 这道题和[昨天的题](https://blog.domineto.top/leetcode/881.html)是同一种题，所以可以直接用 DFS 来解： ```c++ class Solution { public: std::vector<std::vector<int>> combinationSum3(int k, int n) { if (n < k * (k - 1) / 2 + k || n > k * (k - 1) / 2 + (10 - k) * k) return {}; std::vector<std::vector<int>> res; std::vector<int> combination; std::function<void(const int&, const int&)> dfs = [&] (const int &sum, const int &idx) { if (sum == 0 && combination.size() == k) { res.push_back(combination); return; } if (combination.size() == k || idx > 9) return; dfs(sum, idx + 1); if (sum - idx >= 0) { combination.push_back(idx); dfs(sum - idx, idx + 1); combination.pop_back(); } }; dfs(n, 1); return res; } }; ``` 最后修改：2024 年 05 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏