Unique permutation generator

You are midway through a Meta phone screen when the interviewer asks, "Given the array [1, 1, 2], can you generate every distinct rearrangement?" At first glance it sounds identical to the classic permutations problem. Then you notice the repeated 1. Without careful handling, a naive approach would produce [1, 1, 2] twice, once for each copy of 1. This problem, also known as Permutations II on other platforms, tests whether you can extend the standard backtracking template with a pruning strategy that eliminates duplicates before they are ever created.

TL;DR

Sort the input array so duplicate values sit next to each other. Use backtracking with a boolean used array to build permutations one element at a time. At each level, skip an element if it equals the previous element and that previous element is not currently marked as used. This single condition prevents every duplicate permutation without needing a set. The algorithm runs in O(n * n!) time and space.

Why This Problem Matters

Backtracking is the engine behind a whole family of interview problems: subsets, combinations, N-Queens, Sudoku solvers. Permutations II specifically tests whether you can layer a duplicate-pruning strategy on top of the basic backtracking template. Once you internalize this pattern, problems like Combination Sum II and Subsets II become straightforward variations.

Understanding the Problem

Given an array of integers nums that may contain duplicates, return all unique permutations in any order.

Constraints:

• 1 ≤ nums.length ≤ 9
• -10 ≤ nums[i] ≤ 10

For example:

permuteUnique([1,1,2]) => [[1,1,2], [1,2,1], [2,1,1]]
permuteUnique([1,2,3]) => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

With [1, 1, 2], there are only 3 unique permutations rather than the 6 you would get from three distinct elements. The repeated 1 cuts the count in half.

Edge Cases

1. Single element: [5] produces just [[5]]
2. All identical: [0, 0, 0, 0] produces a single permutation [[0, 0, 0, 0]]
3. All unique: Degenerates to the standard permutations problem with n! results
4. Negative numbers: [-1, 2, -1, 2] still works since sorting handles negatives naturally

Solution Approach

The approach has two parts: the standard backtracking skeleton and the duplicate-skipping rule that makes it work with repeated elements.

Step 1: Sort the Array

Sorting is the foundation of the pruning strategy. When duplicates are adjacent, a single comparison catches them.

After sorting [1, 1, 2], the two 1s are next to each other. This adjacency is what makes the skip condition possible.

Step 2: Backtracking with a Used Array

We maintain a boolean array used of the same length as nums. At each recursive call, we iterate through every index. If an element is already used in the current permutation, we skip it. Otherwise, we mark it as used, add it to the current path, recurse, then undo both actions. This choose-explore-unchoose cycle is the heart of backtracking.

The diagram above traces one path through the recursion. After reaching a complete permutation [1, 1, 2], the algorithm backtracks by removing 2, then continues exploring other branches.

Step 3: The Duplicate-Skipping Condition

Here is where this problem diverges from standard permutations. The condition is:

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

This says: if the current element is the same as the previous one, and the previous one is not in the current partial permutation, skip the current one. Why? Because any permutation you would build by using the current element instead of the previous one has already been (or will be) generated when the previous element was chosen first.

In the diagram, index 0 and index 1 both hold the value 1. When building from the empty state, we pick index 0 (the first 1) and proceed. When the loop reaches index 1, it sees nums[1] == nums[0] and !used[0] (because we already backtracked from index 0), so it skips index 1 entirely. This prevents generating the same subtree twice.

The Full Decision Tree

Here is the complete recursion tree for [1, 1, 2]:

Only three leaves reach the bottom level, corresponding to the three unique permutations: [1,1,2], [1,2,1], and [2,1,1]. Every duplicate branch was pruned before it was explored.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

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

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

    for (int i = 0; i < nums.length; i++) {
      // Skip already-used elements
      if (used[i]) continue;

      // Skip duplicates: only use nums[i] if the previous identical value was already used
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      current.add(nums[i]);
      backtrack(nums, used, current, result);
      current.remove(current.size() - 1);
      used[i] = false;
    }
  }
}

Let's walk through this with [1, 1, 2]:

1. Sort: Array is already [1, 1, 2].
2. First level: Pick index 0 (value 1). Skip index 1 because nums[1] == nums[0] and !used[0]. Pick index 2 (value 2).
3. Under index 0: Pick index 1 (value 1), then pick index 2 (value 2). That gives [1, 1, 2]. Backtrack. Pick index 2 (value 2), then pick index 1 (value 1). That gives [1, 2, 1].
4. Under index 2: Pick index 0 (value 1), then pick index 1 (value 1). That gives [2, 1, 1]. Index 1 is not skipped here because index 0 IS used in the current path.

Three permutations total, no duplicates.

Complexity Analysis

Time Complexity: O(n * n!)

In the worst case (all unique elements), there are n! permutations. Each permutation requires O(n) work to copy into the result list. The sorting step is O(n log n), which is dominated by O(n * n!). When duplicates exist, fewer permutations are generated, but the upper bound remains O(n * n!).

Space Complexity: O(n * n!)

The output stores up to n! permutations of length n. The recursion stack goes at most n levels deep, and the used array takes O(n) space. Both are overshadowed by the output size.

Common Pitfalls

1. Forgetting to sort: The skip condition nums[i] == nums[i - 1] only works when duplicates are adjacent. Without sorting, you will still get duplicate permutations.

2. Wrong skip condition: Using used[i - 1] (true) instead of !used[i - 1] (false). Both actually produce correct results, but !used[i - 1] prunes more aggressively and runs faster. The version with used[i - 1] allows the second duplicate to be placed before the first, generating the same set of permutations but exploring more branches.

3. Modifying the input permanently: Some languages pass arrays by reference. If you sort nums in place, make sure that is acceptable. In an interview, mention this to the interviewer.

4. Using a HashSet instead of pruning: Adding each completed permutation to a Set<List<Integer>> technically works but wastes time generating permutations that get thrown away. The sorted + skip approach avoids creating duplicates in the first place.

Interview Tips

1. Start by asking about duplicates: "Can the input contain duplicate values?" This immediately shows you are thinking about edge cases.

2. Explain the two-part strategy: "I will sort to group duplicates, then add a skip condition during backtracking." This frames the solution clearly before you code.

3. Draw the decision tree: Sketch the tree for [1, 1, 2] on the whiteboard. Mark which branches get pruned. Interviewers love visual explanations of recursive algorithms.

4. Mention the alternative: "Another approach uses a frequency map instead of sorting, which avoids the sort step but requires a HashMap." Knowing multiple approaches signals depth.

5. Discuss complexity confidently: State that the output itself requires O(n * n!) space, so no algorithm can do better in terms of space. The pruning only helps wall-clock time.

Key Takeaways

• Sort the array first so duplicates are adjacent. This is the prerequisite for the skip condition to work.
• The skip condition if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue is the only addition needed on top of standard permutation backtracking.
• Backtracking with pruning is always faster than generating all permutations and deduplicating with a set, because pruned branches are never explored.
• This same sort-then-skip pattern appears in Combination Sum II, Subsets II, and other "unique results from duplicates" problems.
• For [0,0,0,0], the algorithm produces exactly one permutation with minimal work. No special case is needed.

Practice and Related Problems

Once you are comfortable with this problem, try these related backtracking challenges:

• Sum Combinations with Repeats (Combination Sum) and Distinct Sum Combinations (Combination Sum II), which apply the same pruning pattern to subset selection
• Power Set Exploration (Subsets), which uses backtracking without the permutation constraint
• Generate Combinations of Parentheses, another classic backtracking problem with different pruning rules

Consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting or preparing for your dream job at a FAANG company, mastering backtracking patterns like this one will set you up for success.

Solutions in Other Languages

Python

class Solution:
    def permute_unique(self, nums):
        result = []
        nums.sort()

        def backtrack(current, used):
            if len(current) == len(nums):
                result.append(current[:])
                return
            for i in range(len(nums)):
                if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                    continue
                used[i] = True
                current.append(nums[i])
                backtrack(current, used)
                current.pop()
                used[i] = False

        backtrack([], [False] * len(nums))
        return result

JavaScript

class Solution {
  permuteUnique(nums) {
    const results = [];
    nums.sort((a, b) => a - b);

    const backtrack = (path, used) => {
      if (path.length === nums.length) {
        results.push([...path]);
        return;
      }
      for (let i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.push(nums[i]);
        backtrack(path, used);
        path.pop();
        used[i] = false;
      }
    };

    backtrack([], Array(nums.length).fill(false));
    return results;
  }
}

TypeScript

class Solution {
  permuteUnique(nums: number[]): number[][] {
    const results: number[][] = [];
    nums.sort((a, b) => a - b);

    const backtrack = (path: number[], used: boolean[]): void => {
      if (path.length === nums.length) {
        results.push([...path]);
        return;
      }
      for (let i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
        used[i] = true;
        path.push(nums[i]);
        backtrack(path, used);
        path.pop();
        used[i] = false;
      }
    };

    backtrack([], Array(nums.length).fill(false));
    return results;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    std::vector<bool> used(nums.size(), false);
    std::vector<int> current;
    backtrack(nums, used, current, result);
    return result;
  }

private:
  void backtrack(std::vector<int>& nums, std::vector<bool>& used,
                 std::vector<int>& current, std::vector<std::vector<int>>& result) {
    if (current.size() == nums.size()) {
      result.push_back(current);
      return;
    }
    for (int i = 0; i < nums.size(); i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      current.push_back(nums[i]);
      backtrack(nums, used, current, result);
      current.pop_back();
      used[i] = false;
    }
  }
};

Go

package solution

import "sort"

func (s *Solution) PermuteUnique(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)
    used := make([]bool, len(nums))
    var backtrack func(path []int)

    backtrack = func(path []int) {
        if len(path) == len(nums) {
            perm := make([]int, len(path))
            copy(perm, path)
            result = append(result, perm)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue
            }
            used[i] = true
            backtrack(append(path, nums[i]))
            used[i] = false
        }
    }

    backtrack([]int{})
    return result
}

type Solution struct{}

Scala

The Scala solution uses a frequency map instead of a boolean used array, which is a more idiomatic functional approach.

class Solution {
  def permuteUnique(nums: Array[Int]): List[List[Int]] = {
    def backtrack(path: List[Int], remaining: Map[Int, Int],
                  result: List[List[Int]]): List[List[Int]] = {
      if (path.length == nums.length) {
        path :: result
      } else {
        remaining.foldLeft(result) { case (acc, (num, count)) =>
          if (count > 0)
            backtrack(num :: path, remaining.updated(num, count - 1), acc)
          else
            acc
        }
      }
    }

    val numCounts = nums.groupBy(identity).view.mapValues(_.length).toMap
    backtrack(Nil, numCounts, Nil)
  }
}

Kotlin

class Solution {
    fun permuteUnique(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        nums.sort()
        backtrack(nums, BooleanArray(nums.size), mutableListOf(), result)
        return result
    }

    private fun backtrack(
        nums: IntArray, used: BooleanArray,
        current: MutableList<Int>, result: MutableList<MutableList<Int>>
    ) {
        if (current.size == nums.size) {
            result.add(current.toMutableList())
            return
        }
        for (i in nums.indices) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue
            used[i] = true
            current.add(nums[i])
            backtrack(nums, used, current, result)
            current.removeAt(current.lastIndex)
            used[i] = false
        }
    }
}

Ruby

class Solution
  def permute_unique(nums)
    result = []
    nums.sort!
    backtrack(nums, Array.new(nums.length, false), [], result)
    result
  end

  private

  def backtrack(nums, used, current, result)
    if current.length == nums.length
      result << current.dup
      return
    end
    nums.each_with_index do |num, i|
      next if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
      used[i] = true
      current << num
      backtrack(nums, used, current, result)
      used[i] = false
      current.pop
    end
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn permute_unique(&self, nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut nums = nums;
        nums.sort();
        Self::backtrack(&nums, &mut vec![false; nums.len()], &mut Vec::new(), &mut result);
        result
    }

    fn backtrack(nums: &[i32], used: &mut Vec<bool>,
                 current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if current.len() == nums.len() {
            result.push(current.clone());
            return;
        }
        for i in 0..nums.len() {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            current.push(nums[i]);
            Self::backtrack(nums, used, current, result);
            current.pop();
            used[i] = false;
        }
    }
}

Swift

class Solution {
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var sortedNums = nums.sorted()
        backtrack(&sortedNums, [Bool](repeating: false, count: nums.count), [], &result)
        return result
    }

    private func backtrack(_ nums: inout [Int], _ used: [Bool],
                           _ current: [Int], _ result: inout [[Int]]) {
        if current.count == nums.count {
            result.append(current)
            return
        }
        for i in 0..<nums.count {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue
            }
            var used = used
            used[i] = true
            var current = current
            current.append(nums[i])
            backtrack(&nums, used, current, &result)
        }
    }
}

C#

using System;
using System.Collections.Generic;

public class Solution {
    public List<List<int>> PermuteUnique(int[] nums) {
        var result = new List<List<int>>();
        Array.Sort(nums);
        Backtrack(nums, new bool[nums.Length], new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] nums, bool[] used,
                           List<int> current, List<List<int>> result) {
        if (current.Count == nums.Length) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = 0; i < nums.Length; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
                continue;
            used[i] = true;
            current.Add(nums[i]);
            Backtrack(nums, used, current, result);
            current.RemoveAt(current.Count - 1);
            used[i] = false;
        }
    }
}

Dart

class Solution {
  List<List<int>> permuteUnique(List<int> nums) {
    List<List<int>> result = [];
    nums.sort();
    _backtrack(nums, List.filled(nums.length, false), [], result);
    return result;
  }

  void _backtrack(List<int> nums, List<bool> used,
                  List<int> current, List<List<int>> result) {
    if (current.length == nums.length) {
      result.add(List.from(current));
      return;
    }
    for (int i = 0; i < nums.length; i++) {
      if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]))
        continue;
      used[i] = true;
      current.add(nums[i]);
      _backtrack(nums, used, current, result);
      current.removeLast();
      used[i] = false;
    }
  }
}

PHP

class Solution {
    public function permuteUnique(array $nums): array {
        $result = [];
        sort($nums);
        $used = array_fill(0, count($nums), false);
        $this->backtrack($nums, $used, [], $result);
        return $result;
    }

    private function backtrack(array $nums, array &$used,
                               array $current, array &$result): void {
        if (count($current) === count($nums)) {
            $result[] = $current;
            return;
        }
        for ($i = 0; $i < count($nums); $i++) {
            if ($used[$i] || ($i > 0 && $nums[$i] === $nums[$i - 1] && !$used[$i - 1]))
                continue;
            $used[$i] = true;
            $current[] = $nums[$i];
            $this->backtrack($nums, $used, $current, $result);
            array_pop($current);
            $used[$i] = false;
        }
    }
}