LeetCode开心刷题十九天——39. Combination Sum40. Combination Sum II

绝地灬酷狼 2023-08-17 15:14 113阅读 0赞

39. Combination Sum

Medium

216868FavoriteShare

Given a set of candidate numbers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

The same repeated number may be chosen from `candidates` unlimited number of times.

Note:

*  All numbers (including `target`) will be positive integers.
 *  The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
    A solution set is:
    [
      [7],
      [2,2,3]
    ]

Example 2:

Input: candidates = [2,3,5], target = 8,
    A solution set is:
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]
    Special Point：
    1.void pop_back();删除最后一个元素
    2.栈，队列用push,vector用push_back
    3.If you face a strange problem,it might because other reasons in the next error,So when
    you don't know how to solve it.Just read more error.Don't just believe compiler.
    4.This function need add & after the definition of vector,only in this way can we change
    the vector's value itself.
    5.use two for loop,to output the value of vector<vector<int>>

#include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<stack>
    #include<string>
    #include<memory>
    #include<memory.h>
    using namespace std;
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>>ans;
            vector<int> cur;
            sort(candidates.begin(),candidates.end());
            dfs(candidates,target,0,cur,ans);
            return ans;
    
        }
    
    private:
        void dfs(vector<int>& candidates,int target,int s,vector<int>& cur,vector<vector<int>>& ans)
        {
            if(target==0)
            {
                ans.push_back(cur);
                return;
            }
            for(int i=s;i<candidates.size();++i)
            {
                if(candidates[i]>target) break;
                cur.push_back(candidates[i]);
                dfs(candidates,target-candidates[i],i,cur,ans);
                cur.pop_back();
            }
    
        }
    
    
    };
    int main()
    {
        Solution s;
        vector<vector<int>> res;
        vector<int> candidates={
         2,3,5};
        res=s.combinationSum(candidates,8);
        vector<int> temp_vect;
        for(vector<vector<int>>::iterator ite=res.begin();ite!=res.end();ite++)
        {
            temp_vect=*ite;
            for(vector<int>::iterator itee=temp_vect.begin();itee!=temp_vect.end();itee++)
            {
                cout<<*itee;
            }
            cout<<endl;
        }
        return 0;
    }

40. Combination Sum II

Medium

91849FavoriteShare

Given a collection of candidate numbers (`candidates`) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

Each number in `candidates` may only be used once in the combination.

Note:

*  All numbers (including `target`) will be positive integers.
 *  The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
    A solution set is:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
    A solution set is:
    [
      [1,2,2],
      [5]
    ]

Special Idea:
    this problem is likely the 39
    We only need to change
    1.vector——》set.Set has special attribute,it can only store unique value and will sorted
    automatically.
    2.the return value cannot be return directly,It need to transverse as vector<vector<int>>(ans.begin(),ans.end());
    3.the attribute vector in dfs function also need to change corresponding.
    4.the recursive i need to change into i+1,means not add itself.

#include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<stack>
    #include<string>
    #include<memory>
    #include<memory.h>
    #include<hash_map>
    #include<map>
    #include<set>
    #include<unordered_map>
    using namespace std;
    class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            set<vector<int>>ans;
            vector<int> cur;
            sort(candidates.begin(),candidates.end());
            dfs(candidates,target,0,cur,ans);
    
            return vector<vector<int>>(ans.begin(),ans.end());
    
        }
    
    private:
        void dfs(vector<int>& candidates,int target,int s,vector<int>& cur,set<vector<int>>& ans)
        {
            if(target==0)
            {
                ans.insert(cur);
                //ans.push(cur);
                return;
            }
            for(int i=s;i<candidates.size();++i)
            {
                if(candidates[i]>target) break;
                cur.push_back(candidates[i]);
                dfs(candidates,target-candidates[i],i+1,cur,ans);
                cur.pop_back();
            }
    
        }
    
    
    };
    int main()
    {
        Solution s;
        vector<vector<int>> res;
        vector<int> candidates={
         10,1,2,7,6,1,5};
        res=s.combinationSum(candidates,8);
        vector<int> temp_vect;
        for(vector<vector<int>>::iterator ite=res.begin();ite!=res.end();ite++)
        {
            temp_vect=*ite;
            for(vector<int>::iterator itee=temp_vect.begin();itee!=temp_vect.end();itee++)
            {
                    cout<<*itee;
            }
            cout<<endl;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11204647.html