加起来和为目标值的组合(二)

C++ 解法, 执行用时: 1ms, 内存消耗: 500KB, 提交时间: 2017-08-16

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<vector<int> > res;
        vector<int> temp;
        dfs(res,num,temp,target,-1);
        return res;
    }
    /*void dfs(vector<vector<int> >&ans, vector<int> &num, vector<int> &path, int sum, int k){
        if(sum==0){
            ans.push_back(path);
        }
        for(int i=k+1;i<num.size();i++){
            if(num[i]<=sum){
                int pre=-1;
                if(num[i]==pre) continue;
                path.push_back(num[i]);
                pre=num[i];
                dfs(ans,num,path,sum-num[i],i);
                path.pop_back();
            }
        }
    }*/
    
    void dfs(vector<vector<int> > &ans,vector<int>&c,vector<int>& path,int sum,int i){
         if(sum==0){
            ans.push_back(path);
            return;
         }
        int pre=-1;
        for(int j=i+1;j<c.size();j++) if(sum>=c[j]){
            if(c[j]==pre) continue;
            pre=c[j];
            path.push_back(c[j]);
            dfs(ans,c,path,sum-c[j],j);
            path.pop_back();
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-07-20

class Solution {
public:
    
    vector<vector<int> > ans;
    vector<int> res;
    
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        
        
        
        sort(num.begin(),num.end());
        DFS(num,target,0,0);
        return ans;

    }
    
    void DFS(vector<int> &num, int target, int m, int cur)  //cur为当前变量，m为循环变量
    { 
        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,num[i]+cur);
                    res.pop_back();
                }
            }
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 512KB, 提交时间: 2021-07-16

class Solution {
    private:
    vector<vector<int>> result;
    vector<int>path;
public:
    void backtracing(vector<int>&num,int target,int sum,int startindex,vector<bool>&used)
    {
        //终止条件
        if(target==sum){
            result.push_back(path);
            return;
        }
        //单层处理
        for(int i=startindex;i<num.size()&&sum+num[i]<=target;i++){
            //排序的思路是正确的没有想到回溯，
            if(i>0&&num[i]==num[i-1]&&used[i-1]==false){//去重
                continue;
            }
            sum+=num[i];
            path.push_back(num[i]);
            used[i]=true;
            backtracing(num, target, sum, i+1, used);
            used[i]=false;
            sum-=num[i];
            path.pop_back();
            
        }

    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        int n=num.size();
        
        
//         vector<vector<int>>result;
//         //首先进行排序
//         //这样做的结果不是本题的意思，本题明显不是保证后面一个数大于前者
//         sort(num.begin(),num.end());//按升序进行排列
//         for(int i=0;i<n;i++){
//             int arr=target-num[i];//记录在当前这个数据下的目标值
//             int left=i+1,right=num.size()-1;
//             while(left<right)
//             {
            
//                vector<int>vec;
                
//                 if(arr-num[left]==num[right])
//                 {
//                     vec.push_back(num[i]);
//                     vec.push_back(num[left]);
//                     vec.push_back(num[right]);
//                     result.push_back(vec);
                    
//                 }
//                 else if(arr-num[left]<num[right])
//                 {
//                     right--;
//                 }else{
//                     left++;
//                 }
                
//             }
            
//         }
//         return result;
        
        
        
        
        //采用dfs+回溯
        vector<bool>used(n,false);
        sort(num.begin(),num.end());
        backtracing(num, target,0,0,used);
        return result;
        
        
        
        
        
        
        
        
        
        
        
        
        
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 540KB, 提交时间: 2021-07-25

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& num, int target, int startIndex){
        if(target == 0){
            res.push_back(path);
            return ;
        }
        if(startIndex >= num.size()) return;
        for(int i = startIndex; i < num.size();i++){
            if(i > startIndex && num[i] == num[i-1]) continue; //去重
            //num = [10,10,10,20,30,50,60] tar =80,第二第三个10在回溯时会重复
            if(num[i] <= target){
                path.push_back(num[i]);
                dfs(num,target-num[i],i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        res.clear();
        path.clear();
        if(num.empty()) return res;
        sort(num.begin(),num.end());
        dfs(num,target,0);
        return res;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 552KB, 提交时间: 2021-07-21

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        if(num.empty())
            return res;
        sort(num.begin(),num.end());
        dfs(num,target,res,tmp,0);
        return res;
    }
    void dfs(vector<int> &num,int target,vector<vector<int>> &res,vector<int> &tmp,int start)
    {
        if(target==0)
        {
            res.push_back(tmp);
            return;
        }
        if(start>=num.size()) return;
        for(int i=start;i<num.size();i++)
        {
            if(i>start&&num[i]==num[i-1])
                continue;
            if(num[i]<=target)
            {
                tmp.push_back(num[i]);
                dfs(num,target-num[i],res,tmp,i+1);
                tmp.pop_back();
            }
        }
    }
};

详情