力扣--深度优先算法/回溯算法39.组合总和

思路分析：

1. 深度优先搜索 (DFS)： 通过递归实现，尝试从给定的数字集合 candidates 中选择可能的数字，构建和为 target 的组合。
2. 递归函数 dfs：
   • 接收参数：candidates 为数字集合，target 为目标和，start 为当前选择的数字起始位置，nownum 为当前组合的和。
   • 遍历当前可能的数字，如果当前数字加上当前组合的和已经超过目标值 target，则跳过当前数字。
   • 将当前数字加入临时结果集 path，更新当前组合的和 nownum。
   • 如果当前组合的和等于目标值 target，将临时结果集加入最终结果集 result。
   • 否则，继续递归生成组合，注意起始位置更新为 i，可以重复使用当前数字。
   • 回溯过程中，撤销选择，继续尝试其他可能的组合。
3. 主函数：
   • 创建空的结果集 result 和临时结果集 path。
   • 调用深度优先搜索函数 dfs，从起始位置 0 和当前和 0 开始生成组合。
   • 返回最终结果。

class Solution {
    // 存储最终结果的二维数组
    vector<vector<int>> result;

    // 存储当前正在生成的组合的临时结果
    vector<int> path;

    // 定义深度优先搜索函数，用于生成组合
    void dfs(vector<int>& candidates, int target, int start, int nownum) {
        // 遍历当前可能的数字
        for (int i = start; i < candidates.size(); i++) {
            // 如果当前数字加上当前和已有和超过目标值 target，则跳过当前数字
            if (candidates[i] + nownum > target)
                continue;

            // 将当前数字加入临时结果集
            path.push_back(candidates[i]);
            nownum += candidates[i];

            // 如果当前和等于目标值 target，则将临时结果集加入最终结果集
            if (nownum == target)
                result.push_back(path);
            else
                // 继续递归生成组合，注意起始位置更新为 i，可以重复使用当前数字
                dfs(candidates, target, i, nownum);

            // 回溯，撤销选择，继续尝试其他可能的组合
            nownum -= candidates[i];
            path.pop_back();
        }
        return;
    }

public:
    // 主函数，生成和为 target 的所有组合
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // 调用深度优先搜索函数，从起始位置 0 和当前和 0 开始生成组合
        dfs(candidates, target, 0, 0);

        // 返回最终结果
        return result;
    }
};