Loading... > https://leetcode.cn/problems/combination-sum/description/?envType=daily-question&envId=2024-04-07 题目需要找到所有可能的组合数，那么直接能想到的就是通过 DFS 来找出所有和为 target 的子集。但直接深搜会导致出现很多重复元素，比如 [1, 2] 和 [2, 1] 的和都是 3 ，但这两个只能算一个解。 那么问题就转化成如何去重了。最直接的思路就是对结果进行去重，但这种方法效率很低，因为对数组的比较非常耗时，且 target 较大时会产生很多重复子集。 直接 DFS 的写法如下 ： ```c++ std::vector<int> combinations; void dfs(const int &target) { if (target == 0) { res.push_back(combination); return; } for (const auto &num : candidates) { if (target - num >= 0) { combinations.push_back(num); dfs(target - num); combinations.pop_back(); } } } ``` 可以看到每次都对 candidates 数组中所有的数进行了搜索，这也就是问题所在 ：直接 DFS 搜索中对顺序是敏感的，而题目需要的结果认为顺序不同也是同一种解。 因此这里只需要改一下搜索方式，剪去重复的解即可： ```c++ std::vector<int> combinations; void dfs(const int &target, const int &idx) { if (idx > candidates.size()) return; if (target == 0) { res.push_back(combination); return; } for (int i = idx; i < n; ++i) { int num = candidates[i]; if (target - num >= 0) { combinations.push_back(num); dfs(target - num, i); combinations.pop_back(); } } } ``` 最后稍微改改，代码如下： ```c++ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { const int n = candidates.size(); 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 (idx == n) return; if (sum == 0) { res.push_back(combination); return; } dfs(sum, idx + 1); if (sum - candidates[idx] >= 0) { combination.push_back(candidates[idx]); dfs(sum - candidates[idx], idx); combination.pop_back(); } }; dfs(target, 0); return res; } }; ``` - 时间复杂度在所有解都满足的情况下是 $O(n \times 2^n)$ ，但实际情况下不可能所有解都满足条件，所以实际的时间复杂度应该和可行解的长度有关。 - 空间复杂度为 $O(target)$ ，最坏的情况下需要递归 target 次。 最后修改：2024 年 05 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏
1 条评论
[...]};时间复杂度 $O(M \times 2^M)$ 。其中 $M$ 为可取数字的范围，本题中固定为 9 。空间复杂度 $O(M)$ 。DFS这道题和昨天的题是同一种题，所以可以直接用 DFS 来解：class Solution {[...]