全排列 II

力扣题目链接

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

解题思路

在上一题的思路上数字有重复，多加上每层判断这个数字有没有在本层使用过即可。

题解

class Solution {
public:vector<vector<int>> ans;vector<int> path;void BackTrack(vector<int> nums, vector<bool>& help){if(path.size() == nums.size()){ans.push_back(path);return;}unordered_map<int, bool> um;for(int i = 0; i < nums.size(); i++){if(help[i] || um[nums[i]]){continue;}path.push_back(nums[i]);help[i] = true;um[nums[i]] = true;BackTrack(nums, help);path.pop_back();help[i] = false;}return;}vector<vector<int>> permuteUnique(vector<int>& nums) {int n = nums.size();vector<bool> help(n, false);BackTrack(nums, help);return ans;}
};