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

   整体思路很简单。一个一个往后加，直到和等于目标值。这其中，若当前和会大于目标值，则跳过当前数组值，与下一个相加。若当前和小于目标值，则继续往后加下一个数。另外一点就是，去重操作，要注意判重条件的确定。此处，因为每次加和时，开头的第一个数可以重复使用，故而通过i > m，判断是否为第一个数。若不为，判断该数是否与前一个数相等，若相等，则考虑后可知，结果会出现重复。就算存在用num[i - 1]时，也用到了num[i]，且num[i]后不再有与num[i - 1]相等的数的这种情况，也已经被考虑在了num[i]中，不会有遗漏，故而放心去重即可。

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
public:
    void Dfs(vector<int> &num, int target, int m, int cur) {
        if (cur == target) {
            ans.push_back(res);
            return ;
        }
        else {
            for (int i = m; i < num.size(); i++) {
                if (cur + num[i] > target)
                    continue;
                if (i > m && num[i-1] == num[i])
                    continue;
                else {
                    res.push_back(num[i]);
                    Dfs(num, target, i + 1, cur + num[i]);
                    res.pop_back();
                }

            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        Dfs(num, target, 0, 0);
        return ans;
    }
};