Permutations II (With Duplicates)

📋

Problem

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.

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

Edge cases: All elements are the same → only one unique permutationArray with no duplicates → all permutations are uniqueEmpty array → returns an empty list or list with empty permutation

</>

IDE

def permuteUnique(nums: list[int]) -> list[list[int]]:public List<List<Integer>> permuteUnique(int[] nums)vector<vector<int>> permuteUnique(vector<int>& nums)function permuteUnique(nums)

def permuteUnique(nums):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> permuteUnique(vector<int>& nums) {
    // Write your solution here
    return {};
}

function permuteUnique(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,1,2],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]Duplicates not skipped during backtracking, causing repeated permutations.✅ Sort input and skip nums[i] if nums[i] == nums[i-1] and used[i-1] is false during recursion.

Wrong: []Empty input returns empty list instead of list with empty permutation.✅ Return [[]] when input is empty to represent one empty permutation.

Wrong: [[5],[5],[5]]Single element input returns duplicates due to incorrect duplicate skipping or recursion.✅ Ensure base case returns single permutation [[nums[0]]] without duplicates.

Wrong: [[2,2,2,2],[2,2,2,2],[2,2,2,2]]All identical elements produce multiple duplicate permutations due to missing skip condition.✅ Skip duplicates by checking if nums[i] == nums[i-1] and used[i-1] is false.

Wrong: [[1,2,2,3],[1,2,3,2],[1,3,2,2]]Greedy approach misses permutations by not exploring all branches.✅ Use full backtracking with used array and duplicate skipping to generate all permutations.

✓

Test Cases

Focus on handling empty and single-element inputs correctly, and test with all identical elements.

Watch out for subtle duplicate skipping bugs and greedy traps; test with mixed duplicates.

Optimize your backtracking to prune duplicates early and avoid generating all permutations blindly.

t1_01basic

Input{"nums":[1,1,2]}

Expected[[1,1,2],[1,2,1],[2,1,1]]

⏱ Performance - must finish in 2000ms

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

💡 Consider sorting the array to handle duplicates effectively.

💡 Use backtracking with a 'used' array to skip duplicates at the same recursion level.

💡 Skip elements if they are the same as previous and previous is not used to avoid duplicate permutations.

Why it failed: Output includes duplicate permutations due to missing skip condition for duplicates. Fix by sorting input and skipping used duplicates in backtracking.

✓ Correct unique permutations generated with proper duplicate skipping.

t1_02basic

Input{"nums":[1,2,3]}

Expected[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

⏱ Performance - must finish in 2000ms

All elements are unique, so all permutations are unique and included.

💡 When no duplicates exist, generate all permutations by swapping or backtracking.

💡 No need to skip duplicates but sorting still helps keep consistent order.

💡 Backtracking with used array or swapping generates all permutations.

Why it failed: Missing some permutations or duplicates present due to incorrect backtracking or skipping logic. Fix by ensuring all unique permutations are generated without skipping unique elements.

✓ All unique permutations generated correctly for distinct elements.

t2_01edge

Input{"nums":[]}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty input returns a list containing an empty permutation.

💡 Check how your code handles empty input arrays.

💡 Base case should return [[]] to represent one empty permutation.

💡 Return [[]] when nums is empty to avoid returning empty list.

Why it failed: Returned empty list instead of list with empty permutation. Fix by returning [[]] for empty input base case.

✓ Correctly returns one empty permutation for empty input.

t2_02edge

Input{"nums":[5]}

Expected[[5]]

⏱ Performance - must finish in 2000ms

Single element array returns one permutation containing that element.

💡 Single element input should return a list with one permutation containing that element.

💡 Base case of recursion should handle length 1 correctly.

💡 Ensure no duplicate skipping logic removes single element permutations.

Why it failed: Returned empty or multiple permutations for single element input. Fix by returning [[nums[0]]] when length is 1.

✓ Correctly returns single permutation for single element input.

t2_03edge

Input{"nums":[2,2,2,2]}

Expected[[2,2,2,2]]

⏱ Performance - must finish in 2000ms

All elements identical, only one unique permutation exists.

💡 When all elements are identical, only one permutation should be returned.

💡 Sorting helps group duplicates and skipping duplicates avoids repeats.

💡 Check skip condition carefully to avoid generating duplicates.

Why it failed: Multiple duplicate permutations returned due to missing or incorrect duplicate skipping. Fix by skipping duplicates when previous identical element is unused.

✓ Correctly returns single unique permutation for all identical elements.

t3_01corner

Input{"nums":[1,1,2,2]}

Expected[[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

⏱ Performance - must finish in 2000ms

Duplicates of two different numbers require careful skipping to avoid duplicate permutations.

💡 Sorting input and using a used array is critical to skip duplicates correctly.

💡 Skip an element if it is the same as previous and previous is not used in current recursion.

💡 This test catches missing skip condition for duplicates at different recursion depths.

Why it failed: Duplicate permutations appear due to missing skip condition for duplicates at recursion level. Fix by checking used[i-1] before including nums[i]. This is the duplicate skipping corner case.

✓ Correctly prunes duplicates and generates all unique permutations.

t3_02corner

Input{"nums":[-1,-1,2]}

Expected[[-1,-1,2],[-1,2,-1],[2,-1,-1]]

⏱ Performance - must finish in 2000ms

Negative duplicates test correct handling of negative numbers and duplicates.

💡 Sorting handles negative numbers correctly as well.

💡 Duplicate skipping logic must work regardless of sign.

💡 Ensure skip condition compares adjacent elements after sorting.

Why it failed: Incorrect handling of negative duplicates causing duplicates or missing permutations. Fix by sorting and applying skip condition uniformly. This is the negative duplicates corner case.

✓ Correctly handles negative duplicates and generates unique permutations.

t3_03corner

Input{"nums":[1,2,2,3]}

Expected[[1,2,2,3],[1,2,3,2],[1,3,2,2],[2,1,2,3],[2,1,3,2],[2,2,1,3],[2,2,3,1],[2,3,1,2],[2,3,2,1],[3,1,2,2],[3,2,1,2],[3,2,2,1]]

⏱ Performance - must finish in 2000ms

Tests that greedy approach picking first available element fails to generate all unique permutations.

💡 Greedy picking without backtracking misses permutations.

💡 Backtracking with used array and skip condition is needed.

💡 Check that all branches are explored, not just first valid choice.

Why it failed: Greedy approach misses permutations by not exploring all branches. Fix by implementing full backtracking with duplicate skipping. This is the greedy trap test.

✓ Full backtracking with duplicate skipping generates all unique permutations.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8]}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum input size n=8 with all unique elements; O(n! * n) complexity must complete within 2 seconds.

💡 Backtracking with pruning is necessary for performance.

💡 Avoid generating duplicates by sorting and skipping.

💡 Use efficient recursion and pruning to avoid TLE.

Why it failed: Brute force or inefficient duplicate filtering causes TLE. Fix by pruning duplicates during backtracking instead of filtering after generation. This is the factorial complexity test.

✓ Algorithm runs within time limit using pruning and backtracking.

Practice

1. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

2. Consider the following BFS-based code snippet for removing invalid parentheses:

from collections import deque

def is_valid(s: str) -> bool:
    count = 0
    for c in s:
        if c == '(': count += 1
        elif c == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

def remove_invalid_parentheses_bfs(s: str):
    res = []
    visited = set([s])
    queue = deque([s])
    found = False

    while queue:
        size = len(queue)
        for _ in range(size):
            curr = queue.popleft()
            if is_valid(curr):
                res.append(curr)
                found = True
            if found:
                continue
            for i in range(len(curr)):
                if curr[i] not in ('(', ')'):
                    continue
                next_str = curr[:i] + curr[i+1:]
                if next_str not in visited:
                    visited.add(next_str)
                    queue.append(next_str)
    return res

print(remove_invalid_parentheses_bfs("()())()"))

What is the output of this code?

easy

A. ["()()()"]

B. ["()()()", "(())()"]

C. ["(())()"]

D. ["()())()"]

Solution

1. Step 1: Trace BFS levels for input "()())()"

   Initial string is invalid. BFS removes one parenthesis at each position generating candidates. The first valid strings found are "()()()" and "(())()".

2. Step 2: Confirm both valid strings are collected

   Since BFS stops adding new states after finding valid strings at current level, both minimal removal results are returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both minimal valid strings are returned [OK]

Hint: BFS returns all minimal valid strings at first valid level [OK]

Common Mistakes:

• Returning only one valid string
• Returning original invalid string
• Missing one minimal valid string

3. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?

def partition(s):
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start, path):
        if start == len(s):
            result.append(path)  # Line X
            return
        for end in range(start, len(s)):
            if is_palindrome(start, end):
                path.append(s[start:end+1])
                backtrack(end+1, path)
                path.pop()

    result = []
    backtrack(0, [])
    return result

medium

A. Line 6: palindrome check misses single character substrings

B. Line X: appending path without copying causes shared references

C. Line 12: for loop range should be from start+1 to len(s)+1

D. Line 15: missing path.pop() after backtrack call

Solution

1. Step 1: Identify how results are stored

   Appending path directly stores a reference, so later modifications affect all stored results.

2. Step 2: Correct approach

   Use result.append(path[:]) to append a copy, preserving each partition snapshot.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Shared references cause incorrect final partitions [OK]

Hint: Always append a copy of path to results [OK]

Common Mistakes:

• Forgetting to copy path before appending
• Incorrect palindrome check boundaries
• Forgetting to pop after recursion

4. Identify the bug in the following code snippet for getPermutation:

medium

A. Line 6: k is not converted to zero-based index before calculations.

B. Line 2: factorial array initialization is incorrect.

C. Line 10: The index calculation uses integer division incorrectly.

D. Line 12: numbers.pop(idx) should be numbers.remove(idx).

Solution

1. Step 1: Check k adjustment

   k must be decremented by 1 to convert to zero-based indexing before using factorial divisions.

2. Step 2: Understand impact of missing k -= 1

   Without this, idx calculation is off by one, leading to incorrect permutation output.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing k -= 1 causes wrong indexing and wrong permutation [OK]

Hint: Always convert k to zero-based before factorial indexing [OK]

Common Mistakes:

• Forgetting zero-based index adjustment
• Misusing pop vs remove
• Incorrect factorial initialization

5. Suppose the problem is modified so that parentheses can be reused multiple times (e.g., you can insert removed parentheses back anywhere). Which of the following algorithmic changes correctly adapts the BFS approach to handle this variant?

hard

A. Switch to backtracking with memoization to explore insertions and removals explicitly, pruning invalid states

B. Use BFS as is, since it already explores all possible removals and insertions implicitly

C. Use a greedy approach to insert parentheses at earliest invalid positions without BFS or backtracking

D. Modify BFS to allow adding parentheses back by generating new states with insertions at every position

Solution

1. Step 1: Understand reuse of parentheses

   Allowing reuse means we can insert parentheses anywhere, greatly increasing state space and complexity.

2. Step 2: Analyze BFS suitability

   Standard BFS only removes characters; it does not handle insertions, so it cannot explore all states correctly.

3. Step 3: Identify correct approach

   Backtracking with memoization can explicitly explore insertions and removals, pruning invalid states to handle reuse properly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with memoization handles insertions and pruning [OK]

Hint: Reuse requires explicit insertion exploration, not just removal BFS [OK]

Common Mistakes:

• Assuming BFS handles insertions
• Using greedy for complex insertions
• Modifying BFS without pruning leads to explosion