组合总数

Myth丶恋晨 2021-11-02 12:32 341阅读 0赞

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。  
解集不能包含重复的组合。   
示例 1:

输入: candidates = \[2,3,6,7\], target = 7,  
所求解集为:  
\[  
  \[7\],  
  \[2,2,3\]  
\]

#include<vector>
    #include<algorithm>
    #include<iostream>
    #include<map>
    #include<set>
    #include<iterator>
    using namespace std;
    map<int,set<vector<int>> > dpkv;
    
    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            set<vector<int> > avectorset;
            // 初始化
            for(int i = 1; i <= target; i++){
                dpkv[i] = avectorset; // 都赋值成一个空的数组
            }
            // 开始递推
            for(int j = 1; j <= target; j++){
                for(vector<int>::iterator it=candidates.begin();it!=candidates.end();it++){
                    if(j==*it){
                        vector<int> one;
                        one.push_back(j);
                        dpkv[j].insert(one);
                    }
                    
                    else if(j>*it){
                        for(set<vector<int>>::iterator its=dpkv[j-*it].begin();its!=dpkv[j-*it].end();its++){
                            vector<int> the_vector=(*its);
                            the_vector.push_back(*it);
                            sort(the_vector.begin(),the_vector.end());
                            dpkv[j].insert(the_vector);   
                        }
                    }
                    
                }
            }
            // 将set加工成vector
            vector<vector<int>> target_v;
            for(set<vector<int> >::iterator its = dpkv[target].begin(); its != dpkv[target].end(); its++){
                target_v.push_back(*its);
            }
                
            return target_v;
        }
    };
    
    
    int main(){
        Solution s;
        vector<int >nums ={2,3,6,7};
        vector<vector<int>> res;
        res=s.combinationSum(nums,7);
        cout<<"success"<<endl;
        for(int i=0;i<res.size();i++){
           for(int j=0;j<res[i].size();j++){
               cout<<res[i][j]<<'\t';   
           }
           cout<<endl;
        }
    }