LeetCode 刷题【40. 组合总和 II】

40. 组合总和 II

自己做

解：递归选取（超内存）

class Solution {
public:
    void dfs(vector<int> &candidates,int target, vector<vector<int>> &res, vector<int> old_combination, vector<int>::iterator idx){        //old_combination是当前组合，res是保存的结果，idx为当前下标索引

        //如果idx等于candidates.end()，说明后面也找不到了，都结束了
         if(idx == candidates.end())
            return;

        //太好了，当前元素就是我们要找的组合中最后一个元素，将其加入结果中
        if(target == *idx){
            old_combination.push_back(*idx);                //加入组合中

            //检查该组合是否已经存在于结果中
            bool exist = false;
            int r_len = res.size();

            for(int i = 0; i < r_len; i++)
                if(res[i].size() == old_combination.size()){        //如果两种组合的长度一致，则有可能重复;长度不一致，必然不重复
                    int c_len = old_combination.size();
                    bool equal = true;
                    for(int j = 0; j < c_len; j++)
                       if(res[i][j] != old_combination[j]){          //存在不一致
                            equal = false;
                            break;
                       }
                    
                    if(equal)                      //如果经过上面的查找发现完全一致【equal不更改为false】，则标记存在重复组合
                        exist = true;

                }
            
            if(!exist)                          //不存在重复组合则存放
                res.push_back(old_combination);                 //将组合放入结果
        }
        //不是我们要找的，或者至少现在不是
        else if(target > *idx){       //比当前大（能继续减去当前元素），往下继续找，否则结束递归
            //不选取的情况，直接继续往后找
            dfs(candidates, target, res, old_combination, idx + 1);

            //选取的情况，这里的将target与当前值相减【这就相当于target减去组合中所有值的和】
            old_combination.push_back(*idx);
            //开始递归
            dfs(candidates, target - *idx, res, old_combination, idx + 1);
        }

        //如果是target < candidate就说明，后面都找不到了直接结束（这里candidate是升序排序）

    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        int len = candidates.size();
        int sum = 0;

        for(int i = 0; i < len; i++)
            sum += candidates[i];

        if(target > sum)            //将全部数加起来都没有target大，后面不用看了，直接返回
            return res;
        
        sort(candidates.begin(),candidates.end());                //排序

        dfs(candidates, target, res, vector<int>(), candidates.begin());         //递归

        return res;
    }
};

看题解

40. 组合总和 II - 力扣（LeetCode）

大佬代码

这里进行递归时，每一轮选取元素时，会对比所有元素进行添加，而且通过if (i > start && choices[i] == choices[i - 1])判断元素是否出现重复，如果重复了就跳过（保证通过i选取的元素是不重复的），要想选重复元素只能通过递归backtrack(state, target - choices[i], choices, i + 1, res)选取，这样选取重复元素时就是连着取了，不可能出现跳着取的情况，这样就避免了子集的重复

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> state;              // 状态（子集）
        sort(candidates.begin(), candidates.end()); // 对 candidates 进行排序
        int start = 0;                  // 遍历起始点
        vector<vector<int>> res;        // 结果列表（子集列表）
        backtrack(state, target, candidates, start, res);
        return res;
    }
private:
    void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {
        // 子集和等于 target 时，记录解
        if (target == 0) {
            res.push_back(state);
            return;
        }
        // 遍历所有选择
        // 剪枝二：从 start 开始遍历，避免生成重复子集
        // 剪枝三：从 start 开始遍历，避免重复选择同一元素
        for (int i = start; i < choices.size(); i++) {
            // 剪枝一：若子集和超过 target ，则直接结束循环
            // 这是因为数组已排序，后边元素更大，子集和一定超过 target
            if (target - choices[i] < 0) {
                break;
            }
            // 剪枝四：如果该元素与左边元素相等，说明该搜索分支重复，直接跳过
            if (i > start && choices[i] == choices[i - 1]) {
                continue;
            }
            // 尝试：做出选择，更新 target, start
            state.push_back(choices[i]);
            // 进行下一轮选择
            backtrack(state, target - choices[i], choices, i + 1, res);
            // 回退：撤销选择，恢复到之前的状态
            state.pop_back();
        }
    }
};