Permutations II

BacktrackingRecursion

25 min

Problem Statement

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

Example

Example 1:

Input: nums = [1,1,2]

[1, 1, 2]

[1, 2, 1]

[2, 1, 1]

Output: [[1,1,2], [1,2,1], [2,1,1]]

Solution

This problem is similar to Permutations, but with the added challenge of handling duplicate numbers. To avoid generating duplicate permutations, we first sort the input array. Then, in our backtracking function, we add a condition to skip an element if it's the same as the previous one and the previous one hasn't been used in this path.

Algorithm Steps

Sort the input array `nums` to handle duplicates easily.
Define a recursive function `backtrack(currentPermutation, used)`.
If the `currentPermutation` has the same length as `nums`, we've found a complete permutation. Add it to our results and return.
Iterate through all numbers in `nums`.
- If the number at index `i` has already been used, skip it.
- **Crucial step for duplicates:** If `i > 0` and `nums[i]` is the same as `nums[i-1]`, and `used[i-1]` is false, skip `nums[i]`. This ensures that we only pick the first of any identical elements.
- Mark `nums[i]` as used.
- Add `nums[i]` to `currentPermutation`.
- Recursively call `backtrack(currentPermutation, used)`.
- Backtrack: remove `nums[i]` from `currentPermutation` and unmark it as used.
Initial call: `backtrack([], new Array(nums.length).fill(false))`.

Permutations II Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Input Array (sorted)

Current Permutation

[]

Unique Permutations

No solutions found yet...

Permutations II Solution


class Solution:
    def permuteUnique(self, nums: list[int]) -> list[list[int]]:
        res = []
        nums.sort()
        
        def backtrack(perm, used):
            if len(perm) == len(nums):
                res.append(perm[:])
                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
                perm.append(nums[i])
                backtrack(perm, used)
                perm.pop()
                used[i] = False
        
        backtrack([], [False] * len(nums))
        return res