How do you solve Permutations II on LeetCode?

Permutations II (LeetCode #47) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n!) time complexity and O(n) space complexity. Key insight: Sorting the array helps to easily identify and skip duplicates.

What is the brute force solution for Permutations II?

The brute force approach for Permutations II is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute-force approach generates all possible permutations of the input array, including duplicates. By using a set to filter out duplicates, we can ensure that only unique permutations are returned. The optimal Optimal Solution approach improves this to O(n!).

What algorithm or data structure is used to solve Permutations II?

Permutations II uses the following concepts: Array, Backtracking, Sorting. The recommended patterns to study are: Backtracking, Sorting.

What are the interview tips for Permutations II?

Always clarify if the input can contain duplicates and how to handle them. Explain your thought process as you write the code; this shows your understanding. Test your solution with edge cases, such as an array with all identical elements.

What are common mistakes when solving Permutations II?

Forgetting to sort the array before generating permutations, leading to duplicates. Not handling the used elements correctly in backtracking, which can lead to infinite loops or incorrect results.

#47

Permutations II

Medium

ArrayBacktrackingSortingBacktrackingSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n!)
Space	O(n)	O(n)

💡

Intuition

Time O(n!)Space O(n)

The optimal solution uses backtracking to generate permutations while avoiding duplicates by skipping over duplicate elements. This is more efficient than generating all permutations and filtering them later.

⚙️

Algorithm

3 steps

1Step 1: Sort the input array to group duplicates together.
2Step 2: Use a backtracking function to build permutations, skipping over duplicate elements to avoid generating the same permutation multiple times.
3Step 3: Store each valid permutation in the result list.

solution.py15 lines

1def permuteUnique(nums):
2    def backtrack(start):
3        if start == len(nums):
4            result.append(nums[:])
5            return
6        for i in range(start, len(nums)):
7            if i > start and nums[i] == nums[start]: continue
8            nums[start], nums[i] = nums[i], nums[start]
9            backtrack(start + 1)
10            nums[start], nums[i] = nums[i], nums[start]
11
12    nums.sort()
13    result = []
14    backtrack(0)
15    return result

ℹ

Complexity note: The time complexity remains O(n!) due to the generation of permutations, but we avoid unnecessary duplicates, making it more efficient in practice. The space complexity is O(n) for storing the permutations.

1Sorting the array helps to easily identify and skip duplicates.
2Backtracking allows us to build permutations incrementally and efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.