力扣每日一题40：组和总数||

题目

中等

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

面试中遇到过这道题?

1/5

是

否

通过次数

526.6K

提交次数

885.9K

通过率

59.4%

思路

正常求这种组合数的方法就是回溯法。先从数组的第一个位置开始递归。对于每一个数，都有选或不选两种选择。由于同一个位置的数在一个组合中不能重复出现，所以当选择这个数的时候，从下一个位置开始递归调用，目标值减了当前数；当不选择这个数的时候，也是从下一个位置开始递归调用，但是目标书不减。

由于数组中会有重复的数，所以用上述方法会有重复的解。

有一个解决方法就是将所有的解都放进一个集合里，然后利用集合的不重复的特性，转换成答案。但是遇到candidates数组重复元素较多的情况时，会进行很多不必要的重复选择，过不了这些样例。

代码（172 / 176 个通过的测试用例）

class Solution {
public:
    //vector<bool> visited;
    void dfs(vector<int>& candidates,int target,set<vector<int>>& combinations,vector<int>& combine,int index)
    {
      if(target==0)
      {//到达了目标就输出一个组合
        combinations.insert(combine);
        return ;
      }
      if(index==candidates.size())
      {//到达了最底层，就没有数字可以用了，返回
        return ;
      }
      //不选择当数字时，直接跳过当前层次
      dfs(candidates,target,combinations,combine,index+1);
      //能选择当前数时
      if(target-candidates[index]>=0)
      {
        //visited[index]=true;
        combine.emplace_back(candidates[index]);
        dfs(candidates,target-candidates[index],combinations,combine,index+1);//选择当前数后，目标减少了
        combine.pop_back();
        //visited[index]=false;
      }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        //visited.resize(candidates.size());
        set<vector<int>> combinations;
        vector<int> combine;
        dfs(candidates,target,combinations,combine,0);//从第零层开始递归
        vector<vector<int>> ans;
        for(auto x:combinations){
            ans.push_back(x);
        }
        return ans;
    }
};

还有一种解决办法就是用一个哈希表记录出现过的数和它出现的次数。这样就可以将相同的数放在一起进行处理，也就是说，如果数 x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0, 1, ⋯ , y 次 x 的递归函数。这样我们就不会得到重复的组合。

除此之外，还可以进行剪枝操作。比如说，3的出现次数是5，而剩余的目标和为7，此时我们只需调用0,1,2次的递归函数即可，不必调用三次以上的递归函数。再比如说，目标值时50，5的出现次数是5，我们也不能调用5次以上的递归函数。还有当前的数大于目标值时，也不可能将当前的数放入列表，这时候直接回溯。

代码（全部样例通过）

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> combina;
    int n;
public:
    void backtrack(int target, int index) {
        if (target == 0) {
            ans.emplace_back(combina);
            return;
        }
        if (index == n || freq[index].first > target) {
            return;
        }

        //不选这个数
        backtrack(target, index + 1);

        //选这个数字
        int cnt = min(target / freq[index].first, freq[index].second);
        for (int i = 1; i <= cnt; i++) {
            combina.emplace_back(freq[index].first);
            backtrack(target - i * freq[index].first, index + 1);
        }
        for (int i = 1; i <= cnt; i++) {
            combina.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        //构造哈希表
        for (auto num : candidates) {
            if (freq.size() == 0 || freq.back().first != num) {
                freq.emplace_back(num, 1);
            }
            else {
                ++freq.back().second;
            }
        }
        n = freq.size();
        backtrack(target, 0);
        return ans;
    }
};