What happens if you not sorting input before skipping duplicates?

Duplicate permutations are generated because duplicates are not adjacent and skipping logic fails Fix: Always sort input before backtracking to group duplicates

What happens if you modifying input array without backtracking swap?

Input array remains changed, causing incorrect permutations Fix: Always swap back after recursion to restore original state

Interview PrepbacktrackingmediumAmazonGoogleMicrosoft

Permutations II (With Duplicates)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Permutations II (With Duplicates)

mediumBACKTRACKINGAmazonGoogleMicrosoft

Imagine you have a collection of colored beads, some colors repeating, and you want to find all unique ways to arrange them on a string without repeating the same pattern twice.

💡 This problem is about generating all unique permutations of a list that may contain duplicates. Beginners often struggle because naive permutation generation produces duplicates, and handling duplicates efficiently requires careful pruning.

📋

Problem Statement

Given a collection of numbers that might contain duplicates, return all possible unique permutations in any order. Input: An array of integers nums. Output: A list of lists, where each list is a unique permutation of nums.

1 ≤ nums.length ≤ 8-10 ≤ nums[i] ≤ 10

💡

Example

Input"[1,1,2]"

Output[[1,1,2],[1,2,1],[2,1,1]]

The input has duplicates (two 1s). The output lists all unique permutations without repetition.

All elements are the same → only one unique permutation
Array with no duplicates → all permutations are unique
Empty array → returns an empty list or list with empty permutation
Array with negative and positive duplicates → handle sign correctly

⚠️

Common Mistakes

Not sorting input before skipping duplicates

Duplicate permutations are generated because duplicates are not adjacent and skipping logic fails

✅ Always sort input before backtracking to group duplicates

Skipping duplicates incorrectly by checking only current and previous without used array

Valid permutations are skipped or duplicates remain

✅ Use 'used' array or 'seen' set at recursion level to correctly skip duplicates

Modifying input array without backtracking swap

Input array remains changed, causing incorrect permutations

✅ Always swap back after recursion to restore original state

Using set to remove duplicates after generating all permutations (brute force)

Solution is correct but inefficient and may time out on large inputs

✅ Prune duplicates during recursion instead of filtering after generation

🧠

Brute Force (Generate All Permutations and Filter Duplicates)

💡 This approach helps understand the problem by first generating all permutations without worrying about duplicates, then removing duplicates afterward. It is simple but inefficient.

Intuition

Generate every possible permutation by swapping elements recursively, then use a set to filter out duplicates at the end.

Algorithm

Recursively generate all permutations by swapping elements.
At each recursion level, swap the current index with all possible indices.
Once a permutation is complete, add it to a result list.
After generating all permutations, convert the list to a set to remove duplicates.

💡 The main challenge is understanding how recursion generates permutations and why duplicates appear when input has repeated elements.

</>

Code

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    # Remove duplicates by converting to set of tuples
    unique_res = list(map(list, set(tuple(lst) for lst in res)))
    return unique_res

# Driver code
if __name__ == '__main__':
    print(permuteUnique([1,1,2]))

Line Notes

def permuteUnique(nums: List[int]) -> List[List[int]]:Defines the function signature with type hints for clarity.

def backtrack(start=0):Starts recursion from index 0 to generate permutations.

if start == len(nums):Base case: when start reaches end, a permutation is complete.

nums[start], nums[i] = nums[i], nums[start]Backtrack by swapping back to restore original state.

backtrack(start + 1)Recurse to fix next element.

unique_res = list(map(list, set(tuple(lst) for lst in res)))Remove duplicates by converting lists to tuples and using a set.

import java.util.*;

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, res);
        // Remove duplicates using a set of strings
        Set<String> set = new HashSet<>();
        for (List<Integer> perm : res) {
            StringBuilder sb = new StringBuilder();
            for (int num : perm) {
                sb.append(num).append(",");
            }
            set.add(sb.toString());
        }
        List<List<Integer>> uniqueRes = new ArrayList<>();
        for (String s : set) {
            String[] parts = s.split(",");
            List<Integer> list = new ArrayList<>();
            for (String part : parts) {
                if (!part.isEmpty()) {
                    list.add(Integer.parseInt(part));
                }
            }
            uniqueRes.add(list);
        }
        return uniqueRes;
    }

    private void backtrack(int[] nums, int start, List<List<Integer>> res) {
        if (start == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) permutation.add(num);
            res.add(permutation);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, res);
            swap(nums, start, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> result = sol.permuteUnique(new int[]{1,1,2});
        System.out.println(result);
    }
}

Line Notes

public List<List<Integer>> permuteUnique(int[] nums)Function signature returning list of unique permutations.

backtrack(nums, 0, res);Start recursive permutation generation from index 0.

// Remove duplicates using a set of stringsConvert each permutation to a string and use a set to remove duplicates.

Set<String> set = new HashSet<>();Initialize a set to store unique permutation strings.

for (List<Integer> perm : res)Iterate over all generated permutations.

StringBuilder sb = new StringBuilder();Build a string representation of the permutation.

set.add(sb.toString());Add the string to the set to ensure uniqueness.

List<List<Integer>> uniqueRes = new ArrayList<>();Prepare list to hold unique permutations.

for (String s : set)Convert each unique string back to a list of integers.

private void backtrack(int[] nums, int start, List<List<Integer>> res)Recursive helper to generate permutations by swapping.

if (start == nums.length)Base case: permutation complete.

swap(nums, start, i);Backtrack by swapping back to original.

backtrack(nums, start + 1, res);Recurse to next position.

private void swap(int[] nums, int i, int j)Helper method to swap two elements in array.

// Driver codeMain method to test the solution.

System.out.println(result);Print the list of unique permutations.

#include <iostream>
#include <vector>
#include <set>
using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        backtrack(nums, 0, res);
        set<vector<int>> unique_res(res.begin(), res.end());
        return vector<vector<int>>(unique_res.begin(), unique_res.end());
    }

    void backtrack(vector<int>& nums, int start, vector<vector<int>>& res) {
        if (start == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, res);
            swap(nums[start], nums[i]);
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<int> nums = {1,1,2};
    vector<vector<int>> result = sol.permuteUnique(nums);
    for (auto &perm : result) {
        for (int num : perm) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> permuteUnique(vector<int>& nums)Function returns all unique permutations.

backtrack(nums, 0, res);Start recursion from index 0.

if (start == nums.size())Base case: permutation complete.

swap(nums[start], nums[i]);Backtrack by swapping back.

backtrack(nums, start + 1, res);Recurse to next position.

set<vector<int>> unique_res(res.begin(), res.end());Remove duplicates by using a set.

return vector<vector<int>>(unique_res.begin(), unique_res.end());Return unique permutations as vector.

function permuteUnique(nums) {
    const res = [];
    function backtrack(start = 0) {
        if (start === nums.length) {
            res.push(nums.slice());
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }
    backtrack();
    // Remove duplicates
    const unique = new Set(res.map(arr => arr.join(',')));
    return Array.from(unique).map(str => str.split(',').map(Number));
}

// Driver code
console.log(permuteUnique([1,1,2]));

Line Notes

function permuteUnique(nums) {Defines the main function.

function backtrack(start = 0) {Recursive helper function starting at index 0.

if (start === nums.length) {Base case: permutation complete.

for (let i = start; i < nums.length; i++) {Loop to swap current index with all possible indices.

[nums[start], nums[i]] = [nums[i], nums[start]];Backtrack by swapping back.

backtrack(start + 1);Recurse to next position.

const unique = new Set(res.map(arr => arr.join(',')));Remove duplicates by converting arrays to strings and using a set.

⏱

Complexity

TimeO(n! * n) due to generating all permutations and copying arrays

SpaceO(n! * n) for storing all permutations before deduplication

We generate all permutations including duplicates, which is n! permutations. Each permutation is copied (O(n)) and stored. Deduplication uses extra space.

💡 For n=8, n! is 40,320, so this approach quickly becomes impractical due to time and memory.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but is useful to understand the problem and recursion basics.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n! * n)`	`O(n! * n)`	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Used Array and Skip	`O(n! * n)`	`O(n! * n)`	Yes	Yes	Code this for clarity and efficiency
3. In-Place Swapping with Skip Set	`O(n! * n)`	`O(n! * n)`	Yes	Yes	Code this for optimal memory and speed

Practice

(1/5)

1. Given the following code snippet, what is the final output of letterCombinations('23')?

from collections import deque

def letterCombinations(digits):
    if not digits:
        return []
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

print(letterCombinations('23'))

easy

A. ['ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf']

B. ['abc', 'def']

C. ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

D. ['a', 'b', 'c', 'd', 'e', 'f']

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace queue after processing digit '2'

Step 2: Trace queue after processing digit '3'

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify algorithm that guarantees solution

Final Answer:

Quick Check:

Solution

Step 1: Trace dfs starting at cell (0,1) 'B'

Step 2: Explore neighbors for next chars 'E' and 'F'

Final Answer:

Quick Check:

Solution

Step 1: Identify branching factor per row

Step 2: Calculate total recursive calls

Final Answer:

Quick Check:

Solution

Step 1: Identify the main operations

Step 2: Sum up the operations

Final Answer:

Quick Check: