We sort the array and use a used array to track which elements are in the current permutation. To avoid duplicates, we skip an element if it's the same as the previous one and the previous one hasn't been used at the current level.
- Sort
nums. - Use a boolean
usedarray. - At each position, try each unused element.
- Skip if
nums[i] == nums[i-1]andused[i-1]is False (avoids duplicate permutations). - Add element, mark used, recurse, then backtrack.
- Time Complexity: O(N! * N).
- Space Complexity: O(N).
def permute_unique(nums):
result = []
nums.sort()
used = [False] * len(nums)
def backtrack(current):
if len(current) == len(nums):
result.append(current[:])
return
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
current.append(nums[i])
backtrack(current)
current.pop()
used[i] = False
backtrack([])
return result