Leetcode47. full arrangement II

Title Description ：

Given a sequence that can contain repeating numbers nums , In any order Returns all non repeating permutations .

Ideas

The problem of permutation is to use backtracking .
because nums There may be the same number in the array , So there will be repeated permutations in the full permutation . This requires pruning . Ideas as follows ：
First of all, will nums Array to sort , Keep the same number next to ;
Then, in the process of recursively filling in numbers, you need to traverse every time vis Array to find unused numbers , So we only look for the first of the unused numbers , for example nums = [1, 1, 2], When the first one 1 After all the initial permutations have been found , Start looking for the second 1 The arrangement at the beginning , At this moment vis = [0, 0, 0], Indicates that none of the three numbers are used , But for the first 2 individual 1 Come on , The previous number is the same as it but not used , Explain that this situation has occurred before , Can directly continue skip . The code for pruning is ：

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    
	// prune , Avoid filling in numbers that have been filled in this position 
    continue;
}

Answer key ：

class Solution {
    
    vector<bool> vis;
public:
    void backtrace(int idx, vector<int>& tmp, vector<vector<int>>& ans, vector<int>& nums) {
    
        if (idx == nums.size()) {
    	//idx And size equal , Explain that you have filled in all the numbers , At this time tmp What is stored is a 
        							// Legal answer , Add it to ans Array , And back to .
            ans.emplace_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
    
            if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    
            	// prune , Avoid filling in numbers that have been filled in this position 
                continue;
            }
            if (!vis[i]) {
    
                tmp.emplace_back(nums[i]);
                vis[i] = 1;
                backtrace(idx + 1, tmp, ans, nums);
                vis[i] = 0;
                tmp.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        vector<int> tmp;
        backtrace(0, tmp, ans, nums);
        return ans;
    }
};