Interview must brush algorithm top101 backtracking article top34

A combination containing a collection of repeating elements

Title source ：(leetcode)[https://leetcode.cn/problems/4sjJUc/]

1、 Title Description

Given an array of integers that may have duplicate numbers  candidates  And a target number  target , find  candidates  All can make numbers and  target  The combination of .

candidates  Each number in can only be used once in each combination , A solution set cannot contain duplicate combinations .

2、 Thinking analysis

Train of thought ：DFS

The output data of the example is ordered, so the first thing is to sort the data , Then call DFS Recursive traversal of functions produces every result that appears there , When the condition is met, it will be added to the result array , But there is a problem because it contains repeated arrays , Therefore, repeated arrays are bound to appear in structural data , So it's going to be heavy ,find If the function cannot be found, it will be inserted into the data, but because it needs to be judged every time it is inserted into the array, the time complexity increases .

Train of thought two ： to flash back + recursive
We use it dfs( pos,rest) Represents a recursive function , among pos Indicates that we are currently recursive to the array candidates No pos Number , and rest We also need to choose and for rest Put the number of into the list as a combination ;
For the current second pos Number , We can do it two ways : Choose or not . If we choose this number , So we call dfs(pos+ 1, rest - candidateslpos) Recursion , Note that there must be rest ≥ candidates[pos). If we don't choose this number , So we call dfs(pos+ 1, rest) Recursion ;
Before a recursion begins , If rest The value of is 0, That means we found a sum for target The combination of , Put it in the answer . Before each call to a recursive function , If we choose that number , You need to put it at the end of the list , This list stores all the numbers we selected . In backtracking , If we choose that number , To remove it from the end of the list .

3、 Code implementation

class Solution {
public:

void func(vector<vector<int>> &v,vector<int>&vm,int &&sum,
    vector<int>&nums,vector<int> num,int target,int &&index){
        if(sum>=target){
            if(sum==target){
                if(find(v.begin(),v.end(),vm)==v.end()){
                     v.push_back(vm);
                }
            }
            return;
        }
        for(int i=index;i<nums.size();i++){
                if(num[i]==0){
                    num[i]=1;
                    vm.push_back(nums[i]);
                    func(v,vm,sum+nums[i],nums,num,target,i+1);
                    num[i]=0;
                    vm.pop_back();
                }
            
        }

    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(),candidates.end());
     vector<vector<int>> v;
         vector<int> vs;
          vector<int> num(candidates.size(),0);
        int inex=0;
         func(v,vs,0,candidates,num,target,0);
         return v;
    }
};

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

Full Permutation without duplicate element set

Title source ：leetcode

1、 Problem description ：

Given an array of integers without duplicate numbers nums , Back to its All possible permutations . Sure In any order Return to the answer .

2、 Thinking analysis

Careful observation shows that , The problem of finding different full permutations can be accomplished by exchanging array elements ;
If the array length is n, Exchange the first element with each subsequent element separately , Generate n Different full permutations ; Then the second element is exchanged with each subsequent element , Generate n -1 Different full permutations

3、 Code implementation

class Solution {
public:
    void func(vector<vector<int>> &v,vector<int> &vm,vector<int>&nums,vector<int>&num){
        if(vm.size()==nums.size()){
            v.push_back(vm);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(num[i]==0){
                num[i]=1;
                vm.push_back(nums[i]);
                func(v,vm,nums,num);
                vm.pop_back();
                num[i]=0;
            }
        }

    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> v;
        vector<int> vm;

        vector<int>num(nums.size(),0);
        func(v,vm,nums,num);
        return v;


    }
};