LeetCode 刷题【39. 组合总和】

39. 组合总和

自己做

解：递归为类似两数之和（超时）

class Solution {
public:
    //两数之和
    void countCombination(vector<int> candidates, vector<int>& now_combination, vector<vector<int>>& res, int target) {       //now_combination为当下的组合
        int c_len = candidates.size();
        int n_len = now_combination.size();

        for (int i = 0; i < c_len; i++) {
            if (target == candidates[i]) {    //加上当前元素就符合了组合总和为target
                now_combination.push_back(candidates[i]);

                //将res添加进结果中
                res.push_back(now_combination);
                now_combination.pop_back();      //归位
            }
            else if (candidates[i] > target) {     //之前的组合加上这个数后就比target大了，那后面的数就不用再看了，相加起来必然都比target大
                return;
            }
            else if (candidates[i] < target) {                               //相加起来比target小，那可以继续往下看        
                now_combination.push_back(candidates[i]);                   //添加当前元素
                target -= candidates[i];                                    //target减去组合相加
                countCombination(candidates, now_combination, res, target);        //开始下一轮循环查找
                now_combination.pop_back();      //归位
                target += candidates[i];
            }
        }

    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> now_combination;

        //排序数组
        sort(candidates.begin(), candidates.end());

        countCombination(candidates, now_combination, res, target);

        //得到未去重的结果，这里再去重
        //cout << "未去重" << endl;
        //printResByIterator(res);

        for (auto ptr1 = res.begin(); ptr1 != res.end(); ptr1++) {
            //统计当前组合的各元素分布
            map<int,int> combine1;       //设置一个数组统计各元素的频率
            int len1 = ptr1->size();
            for (int i = 0; i < len1; i++) {
                auto m_ptr = combine1.find((*ptr1)[i]);     //查看当前元素在集合中是否存在

                if (m_ptr == combine1.end())                //不存在，添加
                    combine1.insert(make_pair((*ptr1)[i], 1));    
                else                                      //存在，在原来的基础上+1
                    m_ptr->second++;
            }
            //cout << "当前组合" ;
            //printMap(combine1);

            //对比其他组合
            for (auto ptr2 = ptr1; ptr2 != res.end();) {
                if (ptr1 != ptr2) {
                    map<int, int> combine2;       //设置一个数组统计各元素的频率
                    int len2 = ptr2->size();
                    for (int i = 0; i < len2; i++) {
                        auto m_ptr = combine2.find((*ptr2)[i]);     //查看当前元素在集合中是否存在

                        if (m_ptr == combine2.end())             //不存在
                            combine2.insert(make_pair((*ptr2)[i], 1));
                        else                                     //存在
                            m_ptr->second++;
                    }

                    //cout << "后续组合" << endl;
                    //printMap(combine2);

                    //检查两集合是否相等
                     //判断两个组合元素是否重复
                    map<int, int>::iterator m1_check = combine1.begin();
                    map<int, int>::iterator m2_check = combine2.begin();

                    //集合中默认是升序，直接判断就好
                    bool equal = true;

                    if (combine1.size() == combine2.size())              //元素个数相等，可能重复
                        while (m1_check != combine1.end()) {
                            if (m1_check->first != m2_check->first || m1_check->second != m2_check->second) {      //存在不一致
                                equal = false;
                                break;
                            }
                            m1_check++;
                            m2_check++;
                        }
                    else
                        equal = false;          //元素个数不相等，不可能重复

                    if (equal) {        //出现重复了，消除一个【这里消除后面的组合】
     /*                   cout << "重复组合";
                        printMap(combine2);*/
                        ptr2 = res.erase(ptr2);
                    }
                    else
                        ptr2++;         //无重复，继续往后找
                }
                else
                    ptr2++;
            }

        }

        return res;

    }
};

看题解

官方代码

这里避免了我之前实现去重的时间消耗，通过设定两个分支来划分，而两个分支之间必然不可能重复（比如一个包含元素2，另一个不包含，这两个组合就必然不会重复）

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};