LeetCode 47: Permutations II Solution in Python Explained

Problem Statement

LeetCode 47, Permutations II, is a medium-level problem where you’re given an array of integers nums that may contain duplicates. Your task is to return all unique permutations of the array. Unlike LeetCode 46, duplicates mean some permutations are identical, so you must ensure uniqueness in the result. Return the result as a list of lists in any order.

Constraints

  • 1 <= nums.length <= 8: Array length is between 1 and 8.
  • -10 <= nums[i] <= 10: Each element is between -10 and 10.

Example

Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Explanation: Three unique permutations of [1,1,2].

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: All 6 permutations (no duplicates in input).

Input: nums = [1]
Output: [[1]]
Explanation: Single element has one permutation.

Understanding the Problem

How do you solve LeetCode 47: Permutations II in Python? For nums = [1,1,2], generate unique permutations: [1,1,2], [1,2,1], [2,1,1]. Duplicates (e.g., two 1s) require handling to avoid identical permutations. We’ll explore two approaches: a Backtracking with Duplicate Handling Solution (optimal and primary) and an Alternative with Sorting and Next Permutation (iterative but complex). The backtracking method uses a counter to manage duplicates efficiently.

Solution 1: Backtracking with Duplicate Handling Approach (Primary)

Explanation

Use backtracking with a frequency counter (e.g., Counter) to track available uses of each number. Build permutations by selecting numbers, reducing their count, and backtracking when done, ensuring uniqueness by only adding distinct numbers at each step.

Here’s a flow for [1,1,2]:

Start: []
Add 1: [1] -> [1,1] -> [1,1,2] (add)
Backtrack: [1] -> [1,2] -> [1,2,1] (add)
Backtrack: [] -> [2] -> [2,1] -> [2,1,1] (add)
  1. Initialize Result and Counter.
  • List for permutations, counter for number frequencies.
  1. Backtrack.
  • Build permutation, use counter to avoid duplicates.
  1. Base Case.
  • When permutation length equals nums length, add it.
  1. Return Result.

Step-by-Step Example

Example 1: nums = [1,1,2]

We need [[1,1,2], [1,2,1], [2,1,1]].

  • Goal: Generate unique permutations.
  • Result for Reference: [[1,1,2], [1,2,1], [2,1,1]].
  • Start: nums = [1,1,2], counter = {1:2, 2:1}, result = [], curr = [].
  • Step 1: Try 1.
    • curr = [1], counter = {1:1, 2:1}.
    • Try 1, curr = [1,1], counter = {1:0, 2:1}.
    • Try 2, curr = [1,1,2], add to result, backtrack.
  • Step 2: Backtrack, curr = [1], counter = {1:1, 2:1}.
    • Try 2, curr = [1,2], counter = {1:1, 2:0}.
    • Try 1, curr = [1,2,1], add to result, backtrack.
  • Step 3: Backtrack, curr = [], counter = {1:2, 2:1}.
    • Try 2, curr = [2], counter = {1:2, 2:0}.
    • Try 1, curr = [2,1], counter = {1:1, 2:0}.
    • Try 1, curr = [2,1,1], add to result.
  • Finish: Return [[1,1,2], [1,2,1], [2,1,1]].

Example 2: nums = [1,2,3]

We need all 6 permutations.

  • Start: counter = {1:1, 2:1, 3:1}.
  • Step 1: Generate as in LeetCode 46, no duplicates to skip.
  • Finish: Return [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

from collections import Counter

def permuteUnique(nums: list[int]) -> list[list[int]]:
    # Line 1: Initialize result and counter
    result = []
    counter = Counter(nums)

    # Line 2: Backtracking helper
    def backtrack(curr: list[int]) -> None:
        # Line 3: Base case: full permutation
        if len(curr) == len(nums):
            result.append(curr[:])
            return

        # Line 4: Try each unique number
        for num in counter:
            if counter[num] > 0:
                # Line 5: Use the number
                counter[num] -= 1
                curr.append(num)
                # Line 6: Recurse
                backtrack(curr)
                # Line 7: Backtrack
                curr.pop()
                counter[num] += 1

    # Line 8: Start backtracking
    backtrack([])
    # Line 9: Return all unique permutations
    return result

Alternative: Sorting and Next Permutation Approach

Explanation

Sort the array and use the "next permutation" algorithm (similar to LeetCode 31) iteratively to generate all permutations, skipping duplicates by checking for identical results. This is less intuitive but avoids explicit recursion.

  1. Sort Array.
  2. Generate Permutations.
  • Use next permutation logic, collect unique ones.

3. Return Result.

Step-by-Step Example (Alternative)

For nums = [1,1,2]:

  • Start: Sort nums = [1,1,2], result = [[1,1,2]].
  • Step 1: Next permutation: [1,2,1], add to result.
  • Step 2: Next permutation: [2,1,1], add to result.
  • Step 3: Next would loop back, stop.
  • Finish: Return [[1,1,2], [1,2,1], [2,1,1]].

How the Code Works (Next Permutation)

def permuteUniqueNext(nums: list[int]) -> list[list[int]]:
    # Line 1: Sort array
    nums.sort()
    result = [nums[:]]

    # Line 2: Generate next permutations
    while True:
        # Line 3: Find first decreasing element from right
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i < 0:
            break

        # Line 4: Find number to swap
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1

        # Line 5: Swap
        nums[i], nums[j] = nums[j], nums[i]

        # Line 6: Reverse after i
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

        # Line 7: Add unique permutation
        result.append(nums[:])

    # Line 8: Return result
    return result

Complexity

  • Backtracking:
    • Time: O(n!) – Generate all permutations, pruning duplicates.
    • Space: O(n) – Recursion stack and current permutation.
  • Next Permutation:
    • Time: O(n * n!) – n! permutations, O(n) per step.
    • Space: O(n * n!) – Store all permutations.

Efficiency Notes

Backtracking is O(n!) time with O(n) space, efficient and intuitive for LeetCode 47. Next Permutation is also O(n * n!) time but uses more space for storing results, less preferred due to complexity.

Key Insights

Tips to master LeetCode 47:

  • Handle Duplicates: Use counter or skip at same level.
  • Build Carefully: Ensure uniqueness in backtracking.
  • Full Coverage: Generate all valid permutations.

Additional Example

For nums = [1,2,2]:

  • Goal: [[1,2,2], [2,1,2], [2,2,1]].
  • Backtracking: [1,2,2], [2,1,2], [2,2,1].
  • Result: [[1,2,2], [2,1,2], [2,2,1]].

Edge Cases

  • Single Element: [1] – Return [[1]].
  • All Same: [1,1,1] – Return [[1,1,1]].
  • No Duplicates: [1,2,3] – Return all 6 permutations.

Final Thoughts

The Backtracking with Duplicate Handling solution shines for LeetCode 47 in Python—elegant, efficient, and perfect for handling duplicates. For a related challenge, try LeetCode 46: Permutations to compare with no duplicates! Ready to permute? Solve LeetCode 47 on LeetCode now and test it with [1,1,2] or [2,2,3] to master unique permutations. Dive in and shuffle it up!