https://leetcode.cn/problems/combination-sum/description/?envType=daily-question&envId=2024-04-07

题目需要找到所有可能的组合数，那么直接能想到的就是通过 DFS 来找出所有和为 target 的子集。但直接深搜会导致出现很多重复元素，比如 [1, 2] 和 [2, 1] 的和都是 3 ，但这两个只能算一个解。

那么问题就转化成如何去重了。最直接的思路就是对结果进行去重，但这种方法效率很低，因为对数组的比较非常耗时，且 target 较大时会产生很多重复子集。

直接 DFS 的写法如下 ：

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 搜索中对顺序是敏感的，而题目需要的结果认为顺序不同也是同一种解。

因此这里只需要改一下搜索方式，剪去重复的解即可：

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();
        }
    }
}

最后稍微改改，代码如下：

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 次。