LeetCode Permutations II Solution
Given a collection of numbers, nums
, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Problem Link: https://leetcode.com/problems/permutations-ii/
Solution
Let's fill in the logic for backtracking1:
path_length
: indicates the number of elements inpath
used
: an array storing the status of whether an element is used.is_leaf
:path_length == len(nums)
, whenpath_length
is the same asnums
's length.get_edges
andis_valid
: all elements that are unused (used[i]==Flase
).
In the implementation, we use an array used
to store the whether an element has been used or not.
Everytime we use a number, we add it into the path
and we mark it used
(used[idx] = True
).
Since there are duplicate values, let's apply methods in Deduplication to deduplicate the results.
we want to sort the nums
array so that duplicate elements are consecutive, and only proceed when the current element is the first of its occurrance.
Implementation
1def permuteUnique(self, nums: List[int]) -> List[List[int]]:
2 used = [False] * len(nums)
3 ans = []
4 nums.sort()
5
6 def dfs(path_length, path):
7 if path_length == len(nums):
8 ans.append(path[:])
9 return
10
11 for i in range(0, len(nums)):
12 if used[i]: continue
13 if(i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue
14 path.append(nums[i])
15 used[i] = True
16 dfs(path_length + 1, path)
17 used[i] = False
18 path.pop()
19
20 dfs(0, [])
21 return ans