美文网首页
39. Combination Sum

39. Combination Sum

作者: 刘小小gogo | 来源:发表于2018-08-26 10:44 被阅读0次
    image.png

    注意,sort的时候,千万不要直接改变list,要用临时数组来代替;因为递归过程中后面还要pop_back;

    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> result;
            set<vector<int>> myres;
            if(candidates.empty()) return result;
            vector<int> list;
            dfs(candidates, myres, list, target);
            for(auto iter = myres.begin(); iter != myres.end(); iter++){
                result.push_back(*iter);
            }
            return result;
            
        }
    private:
        void dfs(vector<int>& candidates, set<vector<int>>& myres, vector<int>& list, int now){
            if(now < 0) return;
            if(now == 0){
                vector<int> tmp(list);
                sort(tmp.begin(), tmp.end());//不能改变list, 要用另外的临时数组
                myres.insert(tmp);
                return;
            }
            for(int i = 0; i < candidates.size(); i++){
                if(now < candidates[i] ) continue;
                list.push_back(candidates[i]);
                dfs(candidates, myres, list, now - candidates[i]);
                list.pop_back();
            }
        }
    };
    

    解法二:
    用一个标记,这样可以防止重复的答案,比如[2,2,3] 和[2,3,2]

    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> result;
            vector<int> list;
            if(candidates.empty()) return result;
            sort(candidates.begin(), candidates.end());
            dfs(candidates, result, list, target, 0);
            return result;
            
        }
    private:
        void dfs(vector<int> candidates, vector<vector<int>>& result, vector<int>& list, int cur, int begin){
            if(cur == 0){
                result.push_back(list);
                return;
            }
            for(int i = begin ; i < candidates.size() && candidates[i] <= cur; i++){
                list.push_back(candidates[i]);
                dfs(candidates, result, list, cur - candidates[i],i);//因为这个值可以重复用,一定要注意,既然在了循环里,所以要用的是i,这样可以防止重复的答案。
                list.pop_back();
            }
        }
    };
    

    相关文章

      网友评论

          本文标题:39. Combination Sum

          本文链接:https://www.haomeiwen.com/subject/lttoiftx.html