47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Approach: Backtracking

To avoid generating duplicate permutations, we use backtracking combined with sorting.

Algorithm:

Sort the input array to group duplicates together.
Use backtracking to generate all possible permutations.
Skip over duplicate elements to avoid generating duplicate permutations.

Why not used[i-1]? Because if the previous element of the same value has been used, it means we have already generated all possible permutations with that value in the current position.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        used = [False] * len(nums)

        nums.sort()

        def backtracking(path):
            if len(path) == len(nums):
                ans.append(list(path))
                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

                path.append(nums[i])
                used[i] = True
                backtracking(path)
                path.pop()
                used[i] = False

        backtracking([])

        return ans

Time: $O(n \cdot n!)$ — for each of the $n!$ permutations, we spend $O(n)$ time to build it.
Space: $O(n)$ — the maximum depth of the recursion tree is $n$ .

Last updated on

47. Permutations II

Approach: Backtracking

On this page