LeetCode如何解决组合总和问题

1. 组合总和问题概述

组合总和问题是一种经典的搜索问题，它的目标是给定一组非负整数，查找出它们的组合，使其和等于给定的目标数。例如，给定数组[2, 3, 6, 7]和目标数7，则可以找到[2,2,3]作为一种组合，使它们的和为7。

2. LeetCode解决组合总和问题

LeetCode提供了一系列的解决方案来解决组合总和问题。其中最常见的解决方案是使用递归。在这种方案中，我们将数组分割成两个部分，一部分包含第一个元素，另一部分包含剩余元素。然后，我们递归地考虑这两个部分，直到它们的和等于目标数。

3. 代码实现

下面是使用递归解决组合总和问题的代码实现：

1234567891011121314151617vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        vector<int> cur;
        dfs(nums, target, 0, cur, res);
        return res;
    }
    void dfs(vector<int>& nums, int target, int start, vector<int>& cur, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(cur);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            if (nums[i] <= target) {
                cur.push_back(nums[i]);
                dfs(nums, target - nums[i], i, cur, res);
                cur.pop_back();
            }
        }
    }

在上面的代码中，我们使用了深度优先搜索（DFS）算法来解决组合总和问题。我们从第一个元素开始，尝试每个元素作为一个组合的一部分，然后递归地试图满足剩余的目标数。如果我们找到了一组和为目标数的元素，就将其添加到结果集中，然后继续搜索。