47. Permutations II
Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 1
Acceptance rate: 49.8%
Problem Breakdown
We need to generate all unique permutations of a given list nums. The core challenge is handling duplicates: if the input contains repeated numbers, standard backtracking will produce identical permutation sequences (e.g., swapping two ‘1’s results in the same output). We must ensure every generated sequence appears exactly once.
Inputs: A list of integers (nums).
Outputs: A list of lists containing all unique permutations. Order does not matter for the final set, but internal order within a permutation matters (e.g., [1, 2] is distinct from [2, 1]).
Constraints & Edge Cases:
- Length up to 8 (), meaning complexity is acceptable.
- Values are small integers (-10 to 10).
- Duplicates must be handled; empty input isn’t possible per constraints, but single-element lists should return a list containing one permutation of length 1.
Intuition
A brute-force approach would simply try every index at every position in the recursion tree ( branches). However, with duplicates (e.g., [1, 1]), this generates redundant work because picking nums[0] then nums[1] is functionally identical to picking nums[1] then nums[0].
To optimize:
- Sort the array: This groups duplicate values together (e.g.,
[1, 1, 2]). Now we can easily detect adjacent duplicates during iteration. - Pruning at recursion depth: When iterating through candidates to fill a specific position in our permutation path, if we encounter a value that is identical to the previous candidate and the previous instance hasn’t been used yet in this current recursive level, we skip it. This ensures that for any unique number available at this step, we only explore permutations starting with that number once per recursion depth.
Approach
- Sort
nums: Essential so duplicates are adjacent. - Backtracking Function: Maintain a
path(current permutation) and ausedboolean array to track indices included in the current path. - Base Case: If
len(path)equalsN, append a copy ofpathto results. - Recursive Step: Iterate through all numbers:
- Skip if index is already used (
used[i]). - Duplicate Check: If
nums[i] == nums[i-1]and the previous instance was not used in this specific recursion level (i.e., we are at a new depth where both instances were skipped or one was picked earlier), skip. Specifically, if!used[i-1], it means index is redundant because picking index now would create an identical permutation to what happens when we pick index . - Mark used, recurse, backtrack (unmark).
- Skip if index is already used (
Complexity Analysis
Time: . In the worst case where all elements are distinct, there are permutations. Generating each takes to copy into results and traverse nodes in recursion tree. With duplicates, it is strictly less than or equal to this bound. Given constraints (), this fits well within time limits.
Space: . This accounts for the recursion stack depth (max ) and the used array. We do not count the output storage space in standard complexity analysis, though it is technically proportional to total permutations generated ().
Solution
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# Sort to group duplicates together for easier pruning logic
nums.sort()
res = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
res.append(list(path))
return
for i in range(len(nums)):
# Skip if index is already included in current path
if used[i]:
continue
# Pruning duplicates:
# If this number is same as previous, and the previous instance wasn't used yet at THIS level, skip.
# This ensures we only pick one of a group of identical numbers for a specific position per recursion depth.
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
# Backtrack step: remove from current level to explore other branches
path.pop()
used[i] = False
backtrack([])
return res
Edge Cases Handled
- All Duplicates: Input
[2, 2, 2]. The logic ensures only one permutation[[2, 2, 2]]is generated because every duplicate check skips subsequent identical values if the previous isn’t used. - Single Element: Loop runs once, base case triggers immediately; returns correct single-element list of lists.
- Negative Numbers: Sorting handles negative integers correctly (e.g.,
[-1, -5]sorts to[-5, -1]). The logic depends on value equality (==) which works identically for negatives and positives.