Permutations

📋

Problem

Imagine you are organizing a race and want to list all possible orders in which runners can finish. How many ways can you arrange them, and how do you generate each order?

Given an array of distinct integers nums, return all possible permutations. You can return the answer in any order. Input: An array nums of distinct integers. Output: A list of lists, where each list is a unique permutation of nums.

1 ≤ nums.length ≤ 8All elements of nums are distinct integers

Edge cases: Empty array → [] (no permutations)Single element array → [[element]] (only one permutation)Array with two elements → two permutations swapping order

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [[1,2,3],[1,3,2],[2,1,3]]Greedy approach that stops recursion early or picks only first unused element.✅ In backtracking, loop over all unused elements at each recursion level instead of picking first only.

Wrong: [[1,1,1],[1,1,1],[1,1,1]]Reusing elements multiple times in the same permutation (unbounded instead of 0/1).✅ Use a used array to mark elements as used and prevent reuse in the same path.

Wrong: [[]]Returning a list with an empty permutation for empty input instead of empty list.✅ Return [] immediately if input is empty; do not add empty path as a permutation.

Wrong: [[4,5]]Not exploring all permutations for two elements; missing swapped order.✅ Ensure recursion explores all unused elements at each step.

✓

Test Cases

Focus on handling base cases like empty and single-element arrays correctly.

Watch out for common pitfalls like greedy selection and element reuse.

Prepare for performance challenges with large input sizes and factorial complexity.

t1_01basic

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 6 permutations of the array [1,2,3] are generated by swapping elements recursively.

💡 Think about generating permutations by choosing each element in turn.

💡 Use backtracking with a used array to track which elements are included.

💡 Append current path when its length equals nums length; backtrack after exploring each choice.

Why it failed: Output missing some permutations or duplicates present; likely missing backtracking or used array reset. Fix by ensuring used[i] is reset to False after recursion.

✓ Correctly generates all permutations using backtracking with used array.

t1_02basic

Input{"nums":[4,5]}

Expected[[4,5],[5,4]]

⏱ Performance - must finish in 2000ms

Two elements produce two permutations by swapping their order.

💡 For two elements, permutations are just the original and the swapped order.

💡 Backtracking should explore both choices by marking used elements.

💡 Ensure recursion explores all unused elements at each step.

Why it failed: Only one permutation returned; likely missing recursive calls for all unused elements. Fix by looping over all indices and recursing on unused ones.

✓ Correctly returns both permutations for two elements.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array has no permutations.

💡 Consider what happens when input array is empty.

💡 Backtracking base case should handle zero-length input gracefully.

💡 Return empty list if nums is empty; do not add empty path as a permutation.

Why it failed: Returns [[]] or non-empty output for empty input; fix by returning [] immediately if nums is empty.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"nums":[7]}

Expected[[7]]

⏱ Performance - must finish in 2000ms

Single element array has exactly one permutation: itself.

💡 With one element, only one permutation exists.

💡 Backtracking should append path when length equals nums length.

💡 Ensure base case triggers correctly for single element.

Why it failed: Returns empty list or multiple permutations for single element; fix by appending path when length equals nums length.

✓ Correctly returns single permutation for single element.

t2_03edge

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

Expectednull

⏱ Performance - must finish in 2000ms

Maximum length input with 8 distinct elements; factorial(8)=40320 permutations expected.

💡 Input size at upper constraint boundary.

💡 Algorithm must handle large output efficiently.

💡 Expect factorial growth in output size; optimize recursion and pruning.

Why it failed: Algorithm times out or crashes on max input; fix by using efficient backtracking and pruning.

✓ Handles maximum input size within time and memory limits.

t3_01corner

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

Expected[]

⏱ Performance - must finish in 2000ms

Input contains duplicates which violates problem constraints of distinct integers; no valid permutations expected.

💡 Check if your code assumes all elements are distinct.

💡 Duplicates require careful handling to avoid repeated permutations.

💡 Use a visited set or sort input and skip duplicates during recursion.

Why it failed: Code assumes distinct elements and returns incorrect or duplicate permutations; fix by handling duplicates explicitly or validating input constraints.

✓ Correctly handles duplicates or rejects invalid input as per problem constraints.

t3_02corner

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

Test to catch greedy approach that picks first unused element always, missing permutations.

💡 Greedy approach may pick elements in fixed order, missing permutations.

💡 Backtracking must explore all unused elements at each recursion level.

💡 Ensure recursion loops over all unused indices, not just first available.

Why it failed: Output missing permutations due to greedy selection; fix by looping over all unused elements in recursion.

✓ Backtracking explores all permutations without greedy pruning.

t3_03corner

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

Test to catch confusion between 0/1 and unbounded permutations (reusing elements).

💡 Permutations require each element used exactly once per permutation.

💡 Do not reuse elements multiple times in the same permutation.

💡 Use a used array to track elements already included in current path.

Why it failed: Output includes permutations with repeated elements; fix by marking elements used and not reusing them in same path.

✓ Correctly generates permutations with each element used once.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=8; algorithm must handle O(n! * n) complexity within 2 seconds.

💡 Permutations grow factorially; expect large output.

💡 Optimize recursion and avoid unnecessary copies.

💡 Use pruning and efficient data structures to meet time limits.

Why it failed: Algorithm times out due to factorial complexity; fix by optimizing recursion and minimizing overhead.

✓ Algorithm completes within time limit for n=8 input.

Practice

1. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?

easy

A. Scan from the end to find a pivot where the sequence stops increasing, swap with the smallest greater element on the right, then reverse the suffix.

B. Apply a greedy approach by swapping the first two elements that are out of order from the start.

C. Use dynamic programming to store all permutations and find the next one by memoization.

D. Generate all permutations, sort them, and pick the next one after the current permutation.

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.

2. Step 2: Identify the optimal approach

   The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]

Hint: Next permutation uses pivot-swap-reverse pattern [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using greedy from start fails on suffix order

2. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

3. What is the time complexity of the bitmask-optimized backtracking solution for the N-Queens problem, and why is the common misconception that it is O(n^3) incorrect?

medium

A. O(n^3) because there are three nested loops over rows, columns, and diagonals

B. O(2^n) because bitmasking iterates over all subsets of columns

C. O(n!) because each row places one queen and pruning reduces the search space factorially

D. O(n^2) because each queen placement checks all previous rows and columns

Solution

1. Step 1: Identify the branching factor per row

   Each row places exactly one queen, and pruning avoids invalid columns and diagonals, reducing choices drastically.

2. Step 2: Understand factorial growth

   Because queens cannot share columns, the number of ways to place queens is at most n!; pruning reduces this further but worst-case remains O(n!).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bitmask pruning reduces search to permutations of columns [OK]

Hint: N-Queens search space is permutations, not polynomial loops [OK]

Common Mistakes:

• Assuming nested loops imply cubic time
• Confusing bitmask subsets with full subsets
• Ignoring pruning effect

4. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.

5. Suppose the Sudoku solver is modified so that digits can be reused multiple times in the same row, column, or box (i.e., constraints are relaxed). Which of the following statements about the backtracking algorithm is true?

hard

A. Constraint checks can be removed, and backtracking reduces to brute force filling

B. Heuristic ordering of empty cells becomes unnecessary since constraints are relaxed

C. The existing backtracking with constraint propagation still works correctly without changes

D. The problem becomes trivial and can be solved in linear time by filling all empty cells with '1'

Solution

1. Step 1: Understand effect of relaxing constraints

   Allowing repeated digits removes Sudoku constraints, so no need to check row, column, or box validity.

2. Step 2: Impact on backtracking algorithm

   Backtracking degenerates to brute force filling since any digit can be placed anywhere; constraint propagation is useless.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Relaxed constraints mean no pruning, so backtracking is brute force [OK]

Hint: Relaxed constraints remove pruning, reverting to brute force [OK]

Common Mistakes:

• Assuming heuristics still help
• Thinking problem becomes trivial linear time