Scale Engineer

Permutations II

Med
#0047Time: O(N * N!)Space: O(N * P + N)9 companies
Patterns
Backtracking
Algorithms
Sorting
Data structures
Array
Companies
AdobeAmazonAppleBloomberg

Prompt

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

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

Example 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]]

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a standard permutation generation algorithm and relies on a HashSet to filter out the duplicate permutations. It explores all possible orderings of the elements, even if they lead to permutations that have already been found, and lets the properties of the set handle the uniqueness requirement.

Algorithm

  • Create a HashSet<List<Integer>> to store the unique permutations.
  • Use a standard recursive backtracking function that generates all permutations (including duplicates) by picking numbers for the current permutation.
  • The recursive function backtrack(currentPermutation, nums, used, resultSet) takes the permutation being built, the original numbers, a boolean used array to track usage, and the result set.
  • Base Case: If the currentPermutation's size equals the length of nums, a full permutation is formed. Add a copy of it to the resultSet. The set will automatically discard duplicates.
  • Recursive Step: Iterate through all numbers in the nums array. If a number at index i has not been used (!used[i]):
    • Mark it as used (used[i] = true).
    • Add nums[i] to currentPermutation.
    • Make a recursive call: backtrack(...).
    • Backtrack by removing the number from currentPermutation and un-marking it as used (used[i] = false).
  • After the initial call completes, convert the resultSet to an ArrayList and return it.

Walkthrough

The core idea is to generate every single permutation as if all elements were distinct and then filter out the duplicates. We can use a recursive backtracking method with a used boolean array to keep track of the elements that have been placed in the current permutation.

The recursive function builds a permutation step-by-step. At each step, it iterates through all the numbers in the input array. If a number hasn't been used yet, it's added to the current permutation, and the function calls itself to place the next number. Once a permutation is complete (its size equals the input array's size), it's added to a HashSet. The HashSet ensures that only unique lists are stored. This process continues until all possible permutations have been generated. Finally, the set of unique permutations is converted to a list.

import java.util.*; class Solution {    public List<List<Integer>> permuteUnique(int[] nums) {        Set<List<Integer>> resultSet = new HashSet<>();        boolean[] used = new boolean[nums.length];        backtrack(new ArrayList<>(), nums, used, resultSet);        return new ArrayList<>(resultSet);    }     private void backtrack(List<Integer> currentPermutation, int[] nums, boolean[] used, Set<List<Integer>> resultSet) {        if (currentPermutation.size() == nums.length) {            resultSet.add(new ArrayList<>(currentPermutation));            return;        }         for (int i = 0; i < nums.length; i++) {            if (!used[i]) {                used[i] = true;                currentPermutation.add(nums[i]);                backtrack(currentPermutation, nums, used, resultSet);                currentPermutation.remove(currentPermutation.size() - 1);                used[i] = false; // backtrack            }        }    }}

Complexity

Time

O(N * N!)

Space

O(N * P + N)

Trade-offs

Pros

  • Conceptually simple to understand if familiar with the basic permutation algorithm.

  • The logic for handling duplicates is offloaded to the HashSet, simplifying the recursive part.

Cons

  • Highly inefficient as it generates many duplicate permutations which are then discarded.

  • The time complexity is factorial, O(N * N!), which is very slow for larger N.

  • High space complexity due to storing all unique permutations in a hash set, O(N * N!).

Solutions

public class Solution {    private List < IList < int >> ans = new List < IList < int >> ();    private List < int > t = new List < int > ();    private int[] nums;    private bool[] vis;    public IList < IList < int >> PermuteUnique(int[] nums) {        Array.Sort(nums);        int n = nums.Length;        vis = new bool[n];        this.nums = nums;        dfs(0);        return ans;    }    private void dfs(int i) {        if (i == nums.Length) {            ans.Add(new List < int > (t));            return;        }        for (int j = 0; j < nums.Length; ++j) {            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {                continue;            }            vis[j] = true;            t.Add(nums[j]);            dfs(i + 1);            t.RemoveAt(t.Count - 1);            vis[j] = false;        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem