# 47. Permutations II

• Time: $O(n \cdot n!)$
• Space: $O(n \cdot n!)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector> permuteUnique(vector& nums) { vector> ans; sort(nums.begin(), nums.end()); dfs(nums, vector(nums.size()), {}, ans); return ans; } private: void dfs(const vector& nums, vector&& used, vector&& path, vector>& ans) { if (path.size() == nums.size()) { ans.push_back(path); return; } for (int i = 0; i < nums.size(); ++i) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.push_back(nums[i]); dfs(nums, move(used), move(path), ans); path.pop_back(); used[i] = false; } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public List> permuteUnique(int[] nums) { List> ans = new ArrayList<>(); Arrays.sort(nums); dfs(nums, new boolean[nums.length], new ArrayList<>(), ans); return ans; } private void dfs(int[] nums, boolean[] used, List path, List> ans) { if (path.size() == nums.length) { ans.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; ++i) { if (used[i]) continue; if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.add(nums[i]); dfs(nums, used, path, ans); path.remove(path.size() - 1); used[i] = false; } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: ans = [] used = [False] * len(nums) def dfs(path: List[int]) -> None: if len(path) == len(nums): ans.append(path.copy()) return for i, num in enumerate(nums): if used[i]: continue if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(num) dfs(path) path.pop() used[i] = False nums.sort() dfs([]) return ans