< Back




47. Permutations II

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.