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

这题和组合总和Ⅰ的区别在于两点：
1.同一个数不能重复选；
2.数组中可能可以有重复的数这样会导致重复选。

例如[1,2,1],target为3时，[[1,2],[2,1]]，但是这样两个算是同一组和，而如果用set把重复的去了，又会导致当target为2时，只有[2]，而[1,1]这个答案就忽略了。

那么该怎么办？

思路分析：

1. 深度优先搜索 (DFS)： 通过递归实现，尝试从给定的数字集合 candidates 中选择可能的数字，构建和为 target 的组合。
2. 递归函数 dfs：
   • 接收参数：candidates 为数字集合，target 为目标和，start 为当前选择的数字起始位置，nownum 为当前组合的和。
   • 遍历当前可能的数字，如果当前数字加上当前组合的和已经超过目标值 target，则跳过当前数字。
   • 避免重复选择相同的数字，如果当前数字与前一个数字相同且不是起始位置，则跳过。
   • 将当前数字加入临时结果集 path，更新当前组合的和 nownum。
   • 如果当前组合的和等于目标值 target，将临时结果集加入最终结果集 result。
   • 否则，继续递归生成组合，注意起始位置更新为 i+1。
   • 回溯过程中，撤销选择，继续尝试其他可能的组合。
3. 主函数：
   • 对候选数组进行排序，以确保相同的数字放在一起，方便后续处理。
   • 调用深度优先搜索函数 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)
                break;

            // 避免重复选择相同的数字，如果当前数字与前一个数字相同且不是起始位置，则跳过
            if (i > start && candidates[i] == candidates[i - 1])
                continue;

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

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

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

public:
    // 主函数，生成和为 target 的所有组合，允许重复选择相同的数字
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // 对候选数组进行排序，方便后续处理
        sort(candidates.begin(), candidates.end());

        // 调用深度优先搜索函数 dfs，从起始位置 0 和当前和 0 开始生成组合
        dfs(candidates, target, 0, 0);

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

关键在于这两步：

// 对候选数组进行排序，方便后续处理 sort(candidates.begin(), candidates.end());

// 避免重复选择相同的数字，如果当前数字与前一个数字相同且不是起始位置，则跳过
            if (i > start && candidates[i] == candidates[i - 1])
                continue;

听懂掌声