题目描述

原题链接：39. 组合总和

解题思路

本题的重点是要保证结果与结果之间去重，且一个结果内可含重复数字。去重的方式便是设置下一回遍历的起始位置startIndex，可保证后续再次遍历的结果不会出现之前遍历过的结果，而与 77. 组合（回溯法+剪枝优化）的区别在于77的startIndex 起始为i + 1可保证不出现重复的数字，而本题起始位i可允许出现重复的数字。

剪枝优化： 让数组从小到大排列，当遍历到当前的数相加后，超过目标值，则可认为后序的数与之相加一定会不满足条件，直接退出。

class Solution {
public:
    vector<vector<int>> res;
    unordered_map<int, int> record;
    void backtracking(vector<int> candidates, int target, int startIndex, vector<int> path) {
        if(target == 0) {
            res.push_back(path);
            return ;
        }
        for(int i = statIndex; i < candidates.size(); i++) {
            // 剪枝优化：之后相加的数会超过target，则直接返回
            if(target - candidates[i] < 0)      return ;
            path.push_back(candidates[i]);
            // 因为一个结果内可以包含相同的数字，但结果与结果之间不能为相同集合，所以用下次起始位置为i，保证可含相同数字，但不会用相同结果集合，完成去重
            backtracking(candidates, target - candidates[i], i, path);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        // 先按从小到大排序，保证后续回溯时，按照从小大大增序遍历，可进行提前剪枝
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, path);
        return res;
    }
};

参考文章：39. 组合总和