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 Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?

easy

A. ['((', '))']

B. ['()()', '(())']

C. ['(())', '()()']

D. ['()()', '(()']

Solution

1. Step 1: Trace backtrack calls for n=2

   Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.

2. Step 2: Confirm order and validity

   Both sequences are valid balanced parentheses of length 4, matching expected output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches known valid sequences for n=2 [OK]

Hint: Backtracking generates sequences in DFS order [OK]

Common Mistakes:

• Confusing order of sequences
• Including invalid partial sequences

2. Consider the following bitmask-based backtracking code for n=4. After placing the first queen at row 0, column 1, what is the value of available_positions at row 1 (second recursive call)?

easy

A. 0b1010 (binary 10 decimal)

B. 0b1100 (binary 12 decimal)

C. 0b1001 (binary 9 decimal)

D. 0b1000 (binary 8 decimal)

Solution

1. Step 1: Trace first queen placement at row 0, col 1

   Position bitmask = 0b0010 (decimal 2). Update cols=0b0010, diag1=(0b0010)<<1=0b0100, diag2=(0b0010)>>1=0b0001.

2. Step 2: Compute available_positions at row 1

   available_positions = (0b1111) & ~(cols | diag1 | diag2) = 0b1111 & ~(0b0010 | 0b0100 | 0b0001) = 0b1111 & ~0b0111 = 0b1111 & 0b1000 = 0b1000 (decimal 8). The only available position is column 3 (bit 3).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask after first queen excludes cols 1, diag1 shifted left, diag2 shifted right [OK]

Hint: Bitmask tracks attacked columns and diagonals precisely [OK]

Common Mistakes:

• Miscomputing diagonal shifts
• Off-by-one in bit length
• Confusing cols with diag masks

3. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

4. Consider the following code snippet for the Word Search II problem using backtracking with a Trie. Given the board and words below, what is the content of the result list after the function completes? Board: [['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']] Words: ["oath", "pea", "eat", "rain"]

easy

A. ["eat", "rain"]

B. ["pea", "rain"]

C. ["oath", "pea", "eat", "rain"]

D. ["oath", "eat"]

Solution

1. Step 1: Trace backtracking for "oath" and "eat"

   Starting from 'o' at (0,0), the path "o-a-t-h" exists, so "oath" is found. Similarly, "eat" is found starting at 'e' (1,0) following adjacency.

2. Step 2: Verify "pea" and "rain" are not found

   "pea" and "rain" cannot be formed due to missing adjacency or letters in the board.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected found words [OK]

Hint: Only words with valid adjacency and prefix in Trie appear [OK]

Common Mistakes:

• Assuming all words appear regardless of adjacency.

5. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.

medium

A. O(M * N * 4 * 3^(L-1)) due to pruning and adjacency constraints

B. O(M * N * 4^L * W), where W is the number of words

C. O(M * N * L^2) because each cell explores all prefixes

D. O(M * N * L) since each cell is visited once per character

Solution

1. Step 1: Identify branching factor in backtracking

   From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.

2. Step 2: Calculate complexity with pruning

   Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known complexity from Trie + backtracking analysis [OK]

Hint: Branching factor reduces after first step due to visited constraints [OK]

Common Mistakes:

• Confusing W (number of words) as multiplicative factor in optimal approach.