题解 | #加起来和为目标值的组合#

思路：

题目的主要信息：

从数组num找出所有加起来等于target的组合
每个组合num中每个元素只能用1次
返回的值必须是非递减次序，组合不能重复

方法一：递归+枝剪
具体做法：
对于排序后的num数组中第一个元素，我们可以考虑如果它比target大，那么后续都会比target大，没有加起来等于target的组合；但是如果它比target，我们可以考虑要不要将其加入待选路径（待选组合）中，如果没有加入（重复了），考虑下一个元素，target不变，如果加入了待选路径，考虑下一个元素的时就需要 $target-num[0]$ ，由此转化成了一个子问题，递归结束的点就是 $target=0$ 或者数组遍历结束。
因此，我们可以遍历数组，对于每个数使用递归，找到所有加起来等于目标值的组合，期间需要枝剪掉重复的组合。
图片说明

class Solution {
public:
    vector<vector<int> > res;
    vector<int> path;
    void dfs(int start, int target, vector<int> &num) {
        if (target == 0) {
            res.push_back(path); //target为0，不用再增加路径了，加入答案中
            return;
        }
        for (int i = start; i < num.size() && target - num[i] >= 0; i++) {
            if (i > start && num[i] == num[i - 1]) 
                continue;
            path.push_back(num[i]);
            // 元素不可重复利用，使用下一个
            dfs(i + 1, target - num[i], num);
            path.pop_back(); //回溯
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end()); //排序
        dfs(0, target, num);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n*2^n)$ ，其中sort排序是 $O(nlog_2n)$ ，因为远小于后面二者相乘，因此忽略不计，遍历一次为 $O(n)$ ，树型递归为 $O(2^n)$
空间复杂度： $O(n)$ ，递归栈深度和记录路径的辅助数组

方法二：哈希表+回溯
具体做法：

同样采用方法一的回溯，不过这才我们不直接排序，而是借助map（依赖红黑树的排序）。map中维护的是num数组中的元素及出现次数。
之后我们递归的时候不再遍历数组，而是遍历map，不过由于有的数字在数组有多个，因此我们需要从多到少（即第一次加入全部的该数，依次减少，最后加入一个，因为map有序，后面的数都比它大，遵从题目要求小的在前的目的）将其加入待选路径后再继续递归，这也是一种去重的方式。

class Solution {
public:
    vector<vector<int> > res;
    vector<int> path;
    void dfs(int target, map<int,int>& mp, map<int, int>::iterator iter)
    {
        //递归终止条件,target等于零或小于排序
        if (target == 0)
        {
            res.push_back(path);
            return;
        }
        if(iter == mp.end() || target < iter->first)
            return;
        //从iter迭代器开始向后继续查找，因为map红黑树自动排序，所以是从小到大顺序的
        for(auto i = iter; i != mp.end(); i++)
        {   
            //考虑一个数出现多个时的情况 
            for(int j = i->second; j > 0; j--)   //索引小数在前
            {
                for(int k = 0; k < j; k++)
                    path.push_back(i->first);
                dfs(target - i->first * j, mp, ++i);
                i--; //回溯
                for(int k = 0; k < j; k++)
                    path.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        map<int, int> mp;
        //先把数据的频数用map保存起来
        for(int i = 0; i < num.size(); i++){
            if(mp.find(num[i]) != mp.end())
                mp[num[i]]++;
            else
                mp[num[i]] = 1;
        }
        auto iter = mp.begin();
        //深度优先算法
        dfs(target, mp, iter);
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n*2^n)$ ，其中初始化map是 $O(nlog_2n)$ ，因为远小于后面二者相乘，因此忽略不计，遍历一次map最大为 $O(n)$ ，树型递归为 $O(2^n)$
空间复杂度： $O(n)$ ，递归栈及map的空间