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

NC46 加起来和为目标值的组合

题意分析：

在给定的数组中找到一些子集，这些子集的和等于target

题解一（回溯）：

枚举出所有子集，判断这些子集里面的元素和是不是等于target，等于就加入到最后结果中。

代码实现如下：

void backtrace(vector<int>&nums,vector<int>tmp,int index,vector<vector<int>>&ret,int sum,int target){
    //tmp保存生成的组合，sum为生成的组合总和，index指向num数组要添加的位置
    if(sum==target){
        //当target==sum，加入生成的组合
        ret.push_back(tmp);
    }
    for(int i=index;i<nums.size();i++){
        //tmp加入num[i]
        tmp.push_back(nums[i]);
        //开始回溯
        backtrace(nums,tmp,i+1,ret,sum+nums[i],target);
        //回溯结束后，弹出添加的元素
        tmp.pop_back();
    }
}

vector<vector<int> > combinationSum2(vector<int> &num, int target) {

    vector<int>tmp;
    vector<vector<int>>ret;
    vector<vector<int>>final_ret;
    set<vector<int>>s;
    backtrace(num,tmp,0,ret,0,target);
    for(auto i:ret){
        //因为最后结果需要有序，所以需要排序一下
        sort(i.begin(),i.end());
        s.insert(i);
    }
    for(auto i:s){
        final_ret.push_back(i);
    }
    return final_ret;
}

时间复杂度： $O(2^n)$ ,我们枚举出了每一个子集，子集的数目一共有 $2^n$ 个。

时间复杂度： $O(n)$

上述代码不会被ac，时间开销太大。

题解二（回溯+剪枝）：

有没有办法减少递归的次数？将给定数组排序后，之后再寻找子集。如果当前的子集和已经大于target，说明后面的元素已经没有再被添加进该子集的必要了，因为再大的元素加进去只会使结果变得更大，因此直接返回即可。

void backtrace(vector<int>&nums,vector<int>tmp,int index,vector<vector<int>>&ret,int sum,int target){
    if(sum==target){
        ret.push_back(tmp);
    }
    if(target<sum){
         //当前加入的元素过大，结束回溯，后面的元素也不必进行试探添加
        return ;
    }
    for(int i=index;i<nums.size();i++){
        tmp.push_back(nums[i]);
        backtrace(nums,tmp,i+1,ret,sum+nums[i],target);
        tmp.pop_back();
    }
}

vector<vector<int> > combinationSum2(vector<int> &num, int target) {

    vector<int>tmp;
    vector<vector<int>>ret;
    vector<vector<int>>final_ret;
    set<vector<int>>s;
    sort(num.begin(),num.end());
    backtrace(num,tmp,0,ret,0,target);
    for(auto i:ret){
        sort(i.begin(),i.end());
        s.insert(i);
    }
    for(auto i:s){
        final_ret.push_back(i);
    }
    return ret;
}

时间复杂度： $O(2^n)$ ，虽然我们做了一些剪枝，复杂度降低了，但非确切上界依然是 $O(2^n)$ 。

时间复杂度： $O(n)$ 。