组合总和 II (Leetcode 暴力)

技术文章 1年前 (2020) 完美者
1,447 0

标签:nat   style   pos   i++   ima   cto   and   color   sum   

技术图片

 

dfs暴力,也就是二进制枚举的思想,也就是枚举所有的情况,这个题目有个很好的剪枝,就是先排序,然后在

技术图片这样可以避免答案出现相同的组合。

 

code:

class Solution {
public:
    int p[1000];
    vector<vector<int>> ans;
    vector<int> v;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0,0,0);
        return ans;
    }
    void dfs(vector<int>& ve,int target,int now,int cnt,int pos){
        if(now==target){
            v.clear();
            for(int i=0;i<cnt;i++){
                v.push_back(p[i]);
            }
            
            ans.push_back(v);
            return ;
        }
        for(int i=pos;i<ve.size()&&now+ve[i]<=target;i++){
            if(i>pos&&ve[i]==ve[i-1]) continue ;
            p[cnt]=ve[i];
            dfs(ve,target,now+ve[i],cnt+1,i+1);
        }
    }
};

 

组合总和 II (Leetcode 暴力)

标签:nat   style   pos   i++   ima   cto   and   color   sum   

原文地址:https://www.cnblogs.com/Accepting/p/13648800.html

版权声明:完美者 发表于 2020-09-17 21:24:53。
转载请注明:组合总和 II (Leetcode 暴力) | 完美导航

暂无评论

暂无评论...