Given a list of numbers, nums, we’re asked to find all permutations - it’s possible that the input might contain duplicates.
In order to handle duplicate values, we create a frequency dictionary of the input to track the numbers we can select from for a particular permutation. Then, following our regular backtracking solution, during each recursion, for each number in our frequency dictionary, if we can select from it we add it to our running combination.
During our recursion, if we encounter that our combination is the same size as the input, we add it to our running answer and return immediately. Upon returning to our backtrack location, we add the number we chose from back to our running frequency dictionary for selection later.
The solution is as follows:
from collections import Counter
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans, n = [], len(nums)
def backtrack(s: List[int], c: dict) -> None:
if len(s) == n:
ans.append(s[:])
return
for num in c:
if c[num] > 0:
s.append(num)
c[num] -= 1
backtrack(s, c)
s.pop()
c[num] += 1
backtrack([], Counter(nums))
return ans_ Time Complexity:
O(…) - Reference https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n
_ Space Complexity:
O(n) - Where n is the size of the input.