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

题目主要信息:

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

具体思路:

对于有序的num数组中第一个元素，我们可以考虑如果它比target大，那么后续元素都会比target大，后面就不会有加起来等于target的组合，后面都可以枝剪；但是如果它比target小，我们可以选择要不要将其加入待选路径（待选组合）中，如果没有加入，考虑下一个元素，target不变，如果加入了待选路径，考虑下一个元素的时就需要 $t a r g e t - n u m [0]$ ，由此转化成了一个子问题，递归结束的点就是 $t a r g e t = 0$ 或者数组遍历结束。

step 1：因为输出结果要求有序，因此先对原数组进行排序，使用sort函数。
step 2：将待选组合看成是树的路径，使用递归选取待选路径，递归入口是数组开始下标、target剩余的值，target为0或者数组遍历结束则跳出递归。
step 3：递归过程中从数组开始下标往后遍历数组，对于每个小于target剩余值的元素选择加入路径，并相应改变下一层递归的target值。
step 4：遍历数组过程中遇到大于target剩余值的元素，那后面都大于了，不用继续遍历了，枝剪掉。
step 5：结束一层递归需要弹出路径最后一个元素，因为刚刚加入代表选择它，现在代表不选择它。

递归及枝剪过程可以参考下图： alt

代码实现:

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 (n l o g_{2} n)$ ，因为远小于后面二者相乘，因此忽略不计，遍历一次为 $O (n)$ ，树型递归为 $O (2^{n})$
空间复杂度： $O (n)$ ，递归栈深度和记录路径的辅助数组