Leetcode 47. Permutations II(python+cpp)

题目

解析：

这道题和46唯一的区别就是有重复数字。其实最简单的方法就是在46题的基础上，append result的时候check一下是否已经存在该result，而且这样的解法也能通过submission，不过比较慢
比较标准的解法是，在recursion的每个level上定义一个visited集合，如果当前的元素已经作为当前level的第一个位置的元素出现过，那么直接跳过，就在46的基础上加几行代码就搞定了

python解法如下：
这边python用的46中第二种解法(simple dfs)

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def dfs(nums,curr):if len(nums)==0:ans.append(curr)returnvisited = set()for i in range(len(nums)):if nums[i] in visited:continuevisited.add(nums[i])dfs(nums[:i]+nums[i+1:],curr+[nums[i]])ans = []dfs(nums,[])return ans

C++代码如下：
C++用的46中第一种解法(back tracking)

class Solution {
    
public:vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> ans;back_track(nums,0,ans);return ans;}void back_track(vector<int> nums,int level,vector<vector<int>>& ans){
    if (level==nums.size()){
    ans.push_back(nums);return;}set<int> visited;for (int i=level;i<nums.size();++i){
    if (visited.count(nums[i])) continue;swap(nums[i],nums[level]);back_track(nums,level+1,ans);swap(nums[i],nums[level]);visited.insert(nums[i]);}}
};