重复的元素只有当前面的放了后面的才能放,非法的答案是因为重复元素之间换了位置。给他们定个顺序就不会产生重复
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<int> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
int len = nums.size();
st = vector<int>(len);
sort(nums.begin(), nums.end());
dfs(0,nums);
return res;
}
void dfs(int u , vector<int>& nums)
{
if(u == nums.size())
{
res.push_back(path);
return;
}
for(int i = 0 ;i < nums.size() ; i ++ )
if( i && nums[i] == nums[i - 1] && !st[i - 1]) continue;
else if(!st[i])
{
st[i] = true;
path.push_back(nums[i]);
dfs(u+1, nums);
path.pop_back();
st[i] = false;
}
}
};