Leetcode 40. Combination Sum(组合总和 II)

@Leetcode
Leetcode 40. Combination Sum(组合总和 II)这题与Leetcode 39 Combination Sum(组合总和)的区别是:

难点:集合有重复元素,但还不能有重复的组合。
解决:组合问题为树形结构,“使用过某个元素”在树型结构上有两个维度,一个维度是同一树枝上使用过,另一个是同一层使用过。
题目要求的是组合不能重复,而组合内的元素可以重复。故我们要去重的同一树层的“使用过”。(使用vector<bool> used数组)
注意:树层去重的话,需要对数组排序!

Leetcode 40. Combination Sum(组合总和 II)

回溯三步曲

  • 递归函数参数
vector<bool> used;
void generateSum(vector<int>& candidates, int target, int startIndex, int &sum, vector<int> &p)
  • 递归终止条件
if(sum == target){
           res.push_back(p);
           return;
       }
  • 单层搜索过程
在candidates[i] == candidates[i-1]的情况下:
used[i-1] = true, 说明同一`树枝`candidates[i-1]使用过。
used[i-1] = false, 说明同一`树层`candidates[i-1]使用过。
// 同一树层上去重
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
                continue;
 for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){

            if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
                continue;

            p.push_back(candidates[i]);

            sum = sum + candidates[i];

            used[i] = true;

            generateSum(candidates, target,  i+1, sum, p);//不用i+1了,表示可以取重复的数(与combination的区别之处)

            sum = sum - candidates[i];

            p.pop_back();

            used[i] = false;

        }

全部代码:

class Solution {
private:
    int sum = 0;

    vector<vector<int>> res;
    vector<bool> used;
    void generateSum(vector<int>& candidates, int target, int start, int &sum, vector<int> &p){
        if(sum == target){
            res.push_back(p);
            //cout<<p[0]<<":"<<endl;
            //for(int i = 0; i < p.size(); i++)
                //cout<<p[i];

            cout<<endl;
            //cout<<"return1"<<endl;
            return;
        }
        if(sum > target)
            return;

        for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){

            if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
                continue;

            p.push_back(candidates[i]);

            sum = sum + candidates[i];

            used[i] = true;

            generateSum(candidates, target,  i+1, sum, p);//不用i+1了,表示可以取重复的数(与combination的区别之处)

            sum = sum - candidates[i];

            p.pop_back();

            used[i] = false;


            //else
                //return;
        }

        return;
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        res.clear();
        vector<int> p;

        sort(candidates.begin(), candidates.end()); //排序,让相同的元素挨在一起

        used = vector<bool>(candidates.size(), false);


        generateSum(candidates, target, 0, sum, p);

        return res;
    }
};
上一篇:Lc40_组合总和II


下一篇:HJ94