利用set解法

对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。

具体而言，利用「回溯」算法求解此题的步骤如图所示：

图片说明

对于原数组，从第一个位置（为10）开始选，加入到临时数组arr中，并将目前的求和结果加入到curr中；
在选择了第一个数的基础上，从第二个数开始（为10）继续选择，并将目前的求和结果加入到curr中；
以此类推，若curr的取值大于目标值（如10、10、20、50），说明现有组合无法完成目标，故撤销最后一次选择，重新开始别的选择（从60开始，继续重复上述步骤）；
若满足条件，则将arr加入到最终结果中。

注意：

题目要求最终结果是有序的，因此需要预先对原数组进行排序；
题目要求最终结果不存在重复，因此可以考虑利用数据结构set来进行去重。

基于上述思想，实现代码如下：

class Solution {
public:
    set<vector<int> > res;
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        if (num.empty()) return vector<vector<int>>(res.begin(), res.end());
        vector<int> arr;
        sort(num.begin(), num.end()); // 对原数组排序，使得最终结果为升序
        backtracking(num, target, 0, 0, arr);
        return vector<vector<int>>(res.begin(), res.end());
    }
    void backtracking(vector<int> &num, int target, int curr, int begin, vector<int> &arr) {
        if (curr >= target) {
            if (curr == target) // 如果当前值与目标值相等
                res.insert(arr);
            return;
        }
        for (int i = begin; i < num.size(); i ++) { // 从begin位置开始遍历取值
            arr.push_back(num[i]); // 加入到数组中
            backtracking(num, target, curr + num[i], i + 1, arr); // 从下一位置开始递归
            arr.pop_back(); // 恢复数组
        }
        return;
    }
};

该方法在最坏情况下，需要对每个位置进行“选择”与“不选择”两种操作，时间复杂度为O(2^N)。在C++中，set的底层实现为红黑树，插入元素的时间复杂度为O(logN)；另外，保存答案的时间复杂度为O(N)，而O(N)>O(logN)，故总时间复杂度大约为O(N*(2^N))。

该方法需要定义临时数组arr，且递归过程需要消耗栈空间，因此空间复杂度为O(N)。

不利用set解法

解法一中的set数据结构可以不需要：

在每次选择完成后，若「下一位置与当前位置取值相同，则跳过」，继续进行下一次选择。此部分实现代码如下：

if (i > begin && num[i] == num[i - 1]) // 跳过重复
                continue;

其余思路与前一解法保持一致，实现的代码如下：

class Solution {
public:
    vector<vector<int> > res; 
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        if (num.empty()) return res; 
        vector<int> arr; 
        sort(num.begin(), num.end()); // 对原数组排序，使得最终结果为升序
        backtracking(num, target, 0, 0, arr); 
        return res; 
    }
    void backtracking(vector<int> &num, int target, int curr, int begin, vector<int> &arr) {
        if (curr >= target) {
            if (curr == target) // 如果当前值与目标值相等
                res.push_back(arr); 
            return; 
        }
        for (int i = begin; i < num.size(); i ++) { // 从begin位置开始遍历取值
            if (i > begin && num[i] == num[i - 1]) // 跳过重复
                continue; 
            arr.push_back(num[i]); // 加入到数组中
            backtracking(num, target, curr + num[i], i + 1, arr); // 从下一位置开始递归
            arr.pop_back(); // 恢复数组
        }
        return; 
    }
};

同前文所述，该方法（最坏）时间复杂度为O(N*(2^N))，空间复杂度为O(N)。

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

利用set解法

不利用set解法