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 a numeric string and a target integer. You need to insert binary operators (+, -, *) between digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions efficiently while handling operator precedence and avoiding invalid operands like those with leading zeros?

easy

A. Backtracking with pruning and careful operand parsing to explore all operator insertions

B. Breadth-first search enumerating all possible expressions without pruning

C. Dynamic programming that stores sub-expression results without operator precedence handling

D. Greedy approach that inserts operators at fixed intervals without backtracking

Solution

1. Step 1: Understand problem requirements

   The problem requires exploring all ways to insert operators to reach a target, respecting operator precedence and avoiding invalid operands like those with leading zeros.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning and operand parsing systematically explores all valid expressions, correctly handles precedence (especially multiplication), and prunes invalid paths early.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid expressions with pruning [OK]

Hint: Backtracking explores all operator insertions with pruning [OK]

Common Mistakes:

• Assuming greedy or DP can handle operator precedence and invalid operands

2. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?

easy

A. Use dynamic programming to store subproblems of partial word matches.

B. Use a greedy search that picks the next letter with the highest frequency in the grid.

C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.

D. Search each word independently using DFS without any prefix pruning.

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.

2. Step 2: Identify efficient pruning technique

   Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie pruning reduces search space drastically compared to naive DFS [OK]

Hint: Trie + backtracking prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking greedy or DP alone can solve adjacency constraints efficiently.

3. You are given a 2D grid of characters and a target string. You need to determine if the string can be formed by sequentially adjacent cells (horizontally or vertically) without revisiting any cell. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Backtracking with in-place marking and exploring all four directions

B. Dynamic Programming with memoization to store partial matches

C. Greedy search by always choosing the next matching character closest to the start

D. Breadth-first search (BFS) to explore all possible paths simultaneously

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if a word can be formed by adjacent cells without reuse, which is a classic backtracking scenario.

2. Step 2: Identify suitable algorithm

   Backtracking with in-place marking efficiently explores all paths while preventing revisiting cells, guaranteeing correctness and optimal pruning.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid paths with pruning [OK]

Hint: Backtracking fits adjacency and no-reuse constraints [OK]

Common Mistakes:

• Assuming greedy or DP can solve adjacency constraints optimally

4. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

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

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

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

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

5. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?

medium

A. O(n) because it scans the array a constant number of times

B. O(n log n) because it sorts the suffix after the pivot

C. O(n!) due to generating all permutations

D. O(n^2) because it swaps elements multiple times in nested loops

Solution

1. Step 1: Identify the main operations

   The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).

2. Step 2: Sum up the operations

   All steps are linear scans or swaps, so total time complexity is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No sorting or factorial generation involved, linear scans only [OK]

Hint: Next permutation scans array linearly multiple times [OK]

Common Mistakes:

• Confusing suffix reversal with sorting
• Assuming factorial due to permutations