14.5 Permutations II

14.5.1 Problem Metadata

14.5.2 Description

Given an array of integers that may contain duplicates, return all unique lc-permutations.

14.5.3 Examples

Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]

14.5.4 Constraints

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

14.5.5 Solution - Backtracking with Choose-Explore-Unchoose Pattern

14.5.5.1 Walkthrough

This problem uses the 2-dimensional traversal mental model of backtracking (see Pattern 1: Choose-Explore-Unchoose):

  • Outer dimension (recursion parameter): path.size() - controls how many elements we’ve chosen (depth 0 to n)
  • Inner dimension (for-loop): Iterates through unique values in the frequency map

The backtracking explores a conceptual grid where each row represents depth (number of elements chosen) and each column represents a choice among available unique values. At each depth, we try choosing each value that still has remaining count, recurse to the next depth, then restore the count to try other options.

Key mechanism: Use a frequency map to track available counts of each unique value. For each recursion level, iterate through the map entries and try using each value if its count is greater than 0. Decrement the count before recursing (choose), then increment it back after returning (unchoose). This naturally prevents duplicate permutations since we process each unique value once per level, and the frequency map tracks exactly how many times each value can still be used.

14.5.5.2 Analysis

  • Time Complexity: O(n × n!) - generating up to n! unique permutations, each taking O(n) to build
  • Space Complexity: O(n) for recursion stack, path list, and frequency map

14.5.5.3 Implementation Steps

  1. Build frequency map counting occurrences of each unique value in nums.
  2. Initialize empty result list to store all permutations.
  3. Define backtrack(path, freqMap, result, targetSize):
    1. Base case: If path.size() == targetSize, add a copy of path to result.
    2. Recursive case: For each unique value num in the frequency map:
      • Skip if freqMap.get(num) == 0 (no more instances available)
      • Decrement freqMap.get(num) by 1 (choose)
      • Add num to path (choose)
      • Recursively call backtrack(path, freqMap, result, targetSize) (explore)
      • Remove last element from path (unchoose)
      • Increment freqMap.get(num) by 1 (unchoose)
  4. Call backtrack(new ArrayList<>(), freqMap, result, nums.length) to start, then return result.

14.5.5.4 Code - Java

public List<List<Integer>> permuteUnique(int[] nums) {
    // Build frequency map
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int num : nums) {
        freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
    }

    List<List<Integer>> result = new ArrayList<>();
    backtrack(new ArrayList<>(), freqMap, result, nums.length);
    return result;
}

private void backtrack(List<Integer> path, Map<Integer, Integer> freqMap,
                       List<List<Integer>> result, int targetSize) {
    // Base case: found a complete permutation
    if (path.size() == targetSize) {
        result.add(new ArrayList<>(path));
        return;
    }

    // Try each unique value that has remaining count
    for (Integer num : freqMap.keySet()) {
        if (freqMap.get(num) == 0) {
            continue; // No more instances of this value available
        }

        // Choose: use one instance of this value
        freqMap.put(num, freqMap.get(num) - 1);
        path.add(num);

        // Explore: recurse to next level
        backtrack(path, freqMap, result, targetSize);

        // Unchoose: restore for next iteration
        path.remove(path.size() - 1);
        freqMap.put(num, freqMap.get(num) + 1);
    }
}

14.5.6 Solution - Backtracking with Visited Array

14.5.6.1 Walkthrough

Sort the input so duplicates are adjacent. During backtracking, skip an index i if it equals nums[i-1] and the previous instance has not been used in the current path. This ensures each value positions once per depth.

14.5.6.2 Analysis

  • Time Complexity: O(n ? n!) in worst case
  • Space Complexity: O(n)

14.5.6.3 Implementation Steps

  1. Sort nums, initialize visited boolean array and result lc-list.
  2. backtrack(path):
    1. If path.size() == nums.length, append copy.
    2. For each index i:
      • Skip if visited[i].
      • Skip if i > 0 && nums[i] == nums[i-1] && !visited[i-1] (avoid duplicates).
      • Mark visited, append, recurse, then undo.
  3. Return result.

14.5.6.4 Code - Java

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    boolean[] visited = new boolean[nums.length];
    backtrack(new ArrayList<>(), nums, visited);
    return result;
}

private void backtrack(List<Integer> path, int[] nums, boolean[] visited) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (visited[i]) {
            continue;
        }
        if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
            continue;
        }
        visited[i] = true;
        path.add(nums[i]);
        backtrack(path, nums, visited);
        path.remove(path.size() - 1);
        visited[i] = false;
    }
}