Title Description:

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Algorithm implementation:

Similar to the previous problem, only there may be duplicate elements in a given array. Each element of a given array can only use one. Change the answer to the previous question:

• The number of repetitions to find each element
• In the number of times that can be repeated, after trying to add this element of these times in turn, can we find the solution that matches the current target value in the remaining elements.

class Solution {
public:
    bool combination(vector<int>& candidates, int target, int index_min, vector<int> &oneres, vector<vector<int>> &res){
        if(target == 0){
            res.push_back(oneres);
            return true;
        }
        if(index_min >= candidates.size())return false;
        if(candidates[index_min] > target)return false;
        if(candidates[index_min] == target){
            oneres.push_back(candidates[index_min]);
            res.push_back(oneres);
            oneres.pop_back();
            return true;
        }
        bool flag;
        int j = 1;
        int nummax = int(target/candidates[index_min]);
        while(candidates[index_min + j] == candidates[index_min])j ++;
        int num = min(j, nummax);
        for(int i = 0; i < num; i ++)oneres.push_back(candidates[index_min]);
        target -= candidates[index_min] * num;
        while(num > 0){
            if(combination(candidates, target, index_min + j, oneres, res))
                flag = true;
            oneres.pop_back();
            num --;
            target += candidates[index_min];
        }
        if(combination(candidates, target, index_min + j, oneres, res))
            flag = true;
        return flag;
        
        
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> res;
        if(candidates.empty())return res;
        vector<int> oneres;
        combination(candidates, target, 0, oneres, res);
        return res;
    }
};

In the process of intermediate debugging after writing, it is found that although the answer can be passed, the process repeats many times when judging the occurrence times of some elements. For example, when the current target value is 7 and the index ﹣ min is 1, you need to check the number of repeats of candidates[1]. When the target value is 5 and the index ﹣ min is 1, you need to query the number of repeats of candidates[1]. That is, while (candidates [index [min + J] = = candidates [index [min]) j + +; line 19 is executed multiple times for some elements.

The optimization is as follows: determine the repetition times of each element outside the recursion, and directly pass in the recursion function

class Solution {
public:
    bool combination(vector<int>& candidates, int target, int index_min, vector<int> &oneres, vector<vector<int>> &res, unordered_map<int, int> m){
        if(target == 0){
            res.push_back(oneres);
            return true;
        }
        if(index_min >= candidates.size())return false;
        if(candidates[index_min] > target)return false;
        if(candidates[index_min] == target){
            oneres.push_back(candidates[index_min]);
            res.push_back(oneres);
            oneres.pop_back();
            return true;
        }
        bool flag;
        int j = m[candidates[index_min]];
        int nummax = int(target/candidates[index_min]);
        // while(candidates[index_min + j] == candidates[index_min])j ++;
        int num = min(j, nummax);
        for(int i = 0; i < num; i ++)oneres.push_back(candidates[index_min]);
        target -= candidates[index_min] * num;
        while(num > 0){
            if(combination(candidates, target, index_min + j, oneres, res, m))
                flag = true;
            oneres.pop_back();
            num --;
            target += candidates[index_min];
        }
        if(combination(candidates, target, index_min + j, oneres, res, m))
            flag = true;
        return flag;
        
        
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> res;
        if(candidates.empty())return res;
        vector<int> oneres;
        unordered_map<int, int> m;
        for(int i = 0; i < candidates.size(); i ++){
            m[candidates[i]] ++;
        }
        combination(candidates, target, 0, oneres, res, m);
        return res;
    }
};