Letter Combinations of Phone Number

🎯

Letter Combinations of Phone Number

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have an old phone keypad and want to find all possible letter combinations that a given digit string could represent, like texting on a classic phone.

💡 This problem is a classic example of backtracking where you build all possible combinations by exploring choices at each step. Beginners often struggle because they try to solve it iteratively or get confused about how to explore all branches systematically.

📋

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. The mapping of digits to letters is the same as on the telephone buttons (2 maps to 'abc', 3 to 'def', etc.). Note that digit '1' does not map to any letters.

1 ≤ digits.length ≤ 4digits[i] is a digit in the range ['2', '9']

💡

Example

Input"23"

Outputadaeafbdbebfcdcecf

Digit '2' maps to 'abc', digit '3' maps to 'def'. All combinations of letters from these two sets are returned.

• Empty input string → returns empty list
• Single digit input like '2' → returns letters mapped to that digit
• Input with repeated digits like '22' → returns combinations with repeated letters
• Maximum length input '2345' → returns all combinations from four digits

⚠️

Common Mistakes

Not handling empty input string

Code may crash or return incorrect results

✅ Add early return for empty input

Using string concatenation in recursion without optimization

Excessive memory usage and slower performance

✅ Use mutable string builder or list to build strings

Not backtracking properly (forgetting to remove last character)

Incorrect combinations or duplicates

✅ Remove last character after recursive call to backtrack

Assuming digit '1' or '0' maps to letters

Key errors or invalid output

✅ Validate input digits or skip digits without mappings

Not testing with repeated digits

Missed bugs in combination generation

✅ Test inputs like '22' to ensure repeated digits handled correctly

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem deeply by exploring all possible letter combinations without optimization. It builds intuition for backtracking.

Intuition

At each digit, try every possible letter it maps to, then recursively do the same for the next digit until all digits are processed.

Algorithm

1. Create a mapping from digits to letters.
2. Define a recursive function that takes the current index and the current combination string.
3. If the current index equals the length of digits, add the combination to results.
4. Otherwise, for each letter mapped from the current digit, recurse with the next index and updated combination.

💡 The recursion builds combinations step-by-step, and the base case collects complete combinations.

</>

Code

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'}
    result = []
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        for char in digit_map[digits[index]]:
            backtrack(index + 1, path + char)
    backtrack(0, '')
    return result

# Example usage:
if __name__ == '__main__':
    print(letterCombinations('23'))

Line Notes

if not digits:Handle empty input early to avoid unnecessary processing and return empty list

digit_map = {...}Map digits to their corresponding letters as per phone keypad to know possible letters

result = []Initialize list to store all possible letter combinations

def backtrack(index, path):Define recursive helper to build combinations by exploring letters at each digit

if index == len(digits):Base case: all digits processed, add current combination to results

for char in digit_map[digits[index]]:Try each letter mapped from current digit to explore all branches

backtrack(index + 1, path + char)Recurse to next digit with updated combination string

import java.util.*;
public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        String[] digitMap = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<>();
        backtrack(digits, 0, new StringBuilder(), digitMap, result);
        return result;
    }
    private void backtrack(String digits, int index, StringBuilder path, String[] digitMap, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = digitMap[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
    }
}

Line Notes

if (digits == null || digits.length() == 0)Check for empty input to return early and avoid unnecessary processing

String[] digitMap = ...Array maps digit characters to their letters for quick lookup

List<String> result = new ArrayList<>();Initialize list to store all letter combinations

backtrack(digits, 0, new StringBuilder(), digitMap, result);Start recursion from first digit with empty path builder

if (index == digits.length())Base case: all digits processed, add current combination to results

String letters = digitMap[digits.charAt(index) - '0'];Get letters mapped from current digit

for (char c : letters.toCharArray())Iterate over letters mapped from current digit to explore all options

path.append(c);Add current letter to path before recursion

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.deleteCharAt(path.length() - 1);Backtrack by removing last letter after recursion to explore other branches

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

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        string path;
        backtrack(digits, 0, path, digitMap, result);
        return result;
    }
private:
    void backtrack(const string& digits, int index, string& path, const vector<string>& digitMap, vector<string>& result) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        string letters = digitMap[digits[index] - '0'];
        for (char c : letters) {
            path.push_back(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<string> res = sol.letterCombinations("23");
    for (auto& s : res) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

if (digits.empty()) return {};Return empty vector immediately if input is empty to avoid processing

vector<string> digitMap = {...};Map digits to corresponding letters for quick lookup

vector<string> result;Initialize vector to store all letter combinations

string path;Mutable string to build current combination efficiently

void backtrack(...)Recursive helper function to build combinations by exploring letters at each digit

if (index == digits.size())Base case: all digits processed, add current path to results

string letters = digitMap[digits[index] - '0'];Get letters mapped from current digit

for (char c : letters)Try each letter mapped from current digit to explore all branches

path.push_back(c);Add letter to path before recursion

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.pop_back();Backtrack by removing last letter after recursion to explore other branches

var letterCombinations = function(digits) {
    if (!digits.length) return [];
    const digitMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    const result = [];
    function backtrack(index, path) {
        if (index === digits.length) {
            result.push(path);
            return;
        }
        for (const char of digitMap[digits[index]]) {
            backtrack(index + 1, path + char);
        }
    }
    backtrack(0, '');
    return result;
};

// Example usage:
console.log(letterCombinations('23'));

Line Notes

if (!digits.length) return [];Handle empty input by returning empty array early

const digitMap = {...};Object maps digits to their letters for quick lookup

const result = [];Initialize array to store all letter combinations

function backtrack(index, path)Recursive function to build combinations by exploring letters at each digit

if (index === digits.length)Base case: all digits processed, add current combination to results

for (const char of digitMap[digits[index]])Iterate over letters mapped from current digit to explore all options

backtrack(index + 1, path + char);Recurse to next digit with updated combination string

⏱

Complexity

TimeO(4^n * n)

SpaceO(n)

Each digit can map up to 4 letters (e.g., '7' or '9'), so total combinations are up to 4^n. Each combination is length n, so appending or creating strings takes O(n) time per combination. The recursion stack and path use O(n) space.

💡 For n=3 digits, this means up to 64 combinations, each length 3, so roughly 192 operations to build all strings. The recursion depth is n, so space is proportional to input length.

Interview Verdict: Accepted

Though brute force explores all combinations, it is efficient enough for typical input sizes and is a solid baseline solution.

🧠

Backtracking with StringBuilder / Mutable Path

💡 Using a mutable string builder or similar structure avoids creating new strings at each recursion, improving performance and reducing memory overhead.

Intuition

Instead of concatenating strings (which creates new strings), append and remove characters in place to build combinations.

Algorithm

1. Create digit to letters mapping.
2. Use a mutable string builder to build combinations.
3. At each recursion, append a letter, recurse, then remove the letter to backtrack.
4. Add complete combinations to results when all digits are processed.

💡 This approach is similar to brute force but uses in-place modification to save memory and time.

</>

Code

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'}
    result = []
    path = []
    def backtrack(index):
        if index == len(digits):
            result.append(''.join(path))
            return
        for char in digit_map[digits[index]]:
            path.append(char)
            backtrack(index + 1)
            path.pop()
    backtrack(0)
    return result

# Example usage:
if __name__ == '__main__':
    print(letterCombinations('23'))

Line Notes

if not digits:Return empty list early if input is empty to avoid unnecessary processing

digit_map = {...}Map digits to their corresponding letters for quick lookup

result = []Initialize list to store all letter combinations

path = []Use list to build string efficiently by appending/removing characters in place

def backtrack(index):Recursive function now uses mutable path without passing it explicitly

if index == len(digits):Base case: join path list into string and add to results

for char in digit_map[digits[index]]:Try each letter mapped from current digit to explore all options

path.append(char)Add letter to path before recursion to build combination

backtrack(index + 1)Recurse to next digit with updated path

path.pop()Remove last letter to backtrack after recursion and explore other branches

import java.util.*;
public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        String[] digitMap = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        backtrack(digits, 0, path, digitMap, result);
        return result;
    }
    private void backtrack(String digits, int index, StringBuilder path, String[] digitMap, List<String> result) {
        if (index == digits.length()) {
            result.add(path.toString());
            return;
        }
        String letters = digitMap[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            path.append(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
    }
}

Line Notes

if (digits == null || digits.length() == 0)Check for empty input to return early and avoid unnecessary processing

String[] digitMap = ...Array maps digit characters to their letters for quick lookup

List<String> result = new ArrayList<>();Initialize list to store all letter combinations

StringBuilder path = new StringBuilder();Use mutable string builder to avoid string concatenation overhead

backtrack(digits, 0, path, digitMap, result);Pass mutable path to recursive function to build combinations in place

if (index == digits.length())Base case: all digits processed, add current combination to results

String letters = digitMap[digits.charAt(index) - '0'];Get letters mapped from current digit

for (char c : letters.toCharArray())Iterate over letters mapped from current digit to explore all options

path.append(c);Append letter before recursion to build combination

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.deleteCharAt(path.length() - 1);Remove last letter to backtrack after recursion and explore other branches

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

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> result;
        string path;
        backtrack(digits, 0, path, digitMap, result);
        return result;
    }
private:
    void backtrack(const string& digits, int index, string& path, const vector<string>& digitMap, vector<string>& result) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        string letters = digitMap[digits[index] - '0'];
        for (char c : letters) {
            path.push_back(c);
            backtrack(digits, index + 1, path, digitMap, result);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<string> res = sol.letterCombinations("23");
    for (auto& s : res) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

if (digits.empty()) return {};Return empty vector immediately if input is empty to avoid processing

vector<string> digitMap = {...};Map digits to corresponding letters for quick lookup

vector<string> result;Initialize vector to store all letter combinations

string path;Mutable string to build current combination efficiently

void backtrack(...)Recursive helper uses mutable path to build combinations in place

if (index == digits.size())Base case: all digits processed, add current path to results

string letters = digitMap[digits[index] - '0'];Get letters mapped from current digit

for (char c : letters)Try each letter mapped from current digit to explore all branches

path.push_back(c);Add letter to path before recursion

backtrack(digits, index + 1, path, digitMap, result);Recurse to next digit with updated path

path.pop_back();Remove letter after recursion to backtrack and explore other branches

var letterCombinations = function(digits) {
    if (!digits.length) return [];
    const digitMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    const result = [];
    const path = [];
    function backtrack(index) {
        if (index === digits.length) {
            result.push(path.join(''));
            return;
        }
        for (const char of digitMap[digits[index]]) {
            path.push(char);
            backtrack(index + 1);
            path.pop();
        }
    }
    backtrack(0);
    return result;
};

console.log(letterCombinations('23'));

Line Notes

if (!digits.length) return [];Return empty array early if input is empty to avoid unnecessary processing

const digitMap = {...};Object maps digits to their letters for quick lookup

const result = [];Initialize array to store all letter combinations

const path = [];Use array as mutable path to build strings efficiently by appending/removing characters

function backtrack(index)Recursive function uses mutable path without passing it explicitly

if (index === digits.length)Base case: join path array into string and add to results

for (const char of digitMap[digits[index]])Iterate over letters mapped from current digit to explore all options

path.push(char);Add letter before recursion to build combination

backtrack(index + 1);Recurse to next digit with updated path

path.pop();Remove letter after recursion to backtrack and explore other branches

⏱

Complexity

TimeO(4^n * n)

SpaceO(n)

Same as brute force but reduces overhead of string concatenation by using mutable path. Each digit can map up to 4 letters, so total combinations are up to 4^n. Each combination is length n, so building strings takes O(n) time per combination. The recursion stack and path use O(n) space.

💡 For n=3, this approach is faster and uses less memory than naive string concatenation because it modifies the path in place instead of creating new strings.

Interview Verdict: Accepted

This is a practical optimization that interviewers appreciate, showing attention to detail and efficiency.

🧠

Iterative Approach Using Queue

💡 An iterative approach uses a queue to build combinations level by level, which can be easier to understand for those uncomfortable with recursion.

Intuition

Start with an empty string in a queue, then for each digit, append all possible letters to each string in the queue, updating the queue iteratively.

Algorithm

1. Initialize a queue with an empty string.
2. For each digit, dequeue all current strings and enqueue new strings formed by appending each letter mapped from the digit.
3. After processing all digits, the queue contains all possible combinations.
4. Return the queue as a list.

💡 This approach simulates the recursive tree using a queue and builds combinations level by level.

</>

Code

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)

# Example usage:
if __name__ == '__main__':
    print(letterCombinations('23'))

Line Notes

from collections import dequeUse deque for efficient queue operations (O(1) pops from front)

if not digits:Return empty list early if input is empty to avoid unnecessary processing

digit_map = {...}Map digits to their corresponding letters for quick lookup

queue = deque([''])Initialize queue with empty string as starting point for building combinations

for digit in digits:Process each digit one by one to build combinations level by level

for _ in range(len(queue))Process all current combinations before adding new letters to avoid infinite loop

prev = queue.popleft()Remove front combination to extend with letters from current digit

queue.append(prev + char)Add new combination with appended letter to queue

import java.util.*;
public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        String[] digitMap = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        LinkedList<String> queue = new LinkedList<>();
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            String letters = digitMap[digits.charAt(i) - '0'];
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String prev = queue.poll();
                for (char c : letters.toCharArray()) {
                    queue.add(prev + c);
                }
            }
        }
        return queue;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
    }
}

Line Notes

if (digits == null || digits.length() == 0)Check for empty input to return early and avoid unnecessary processing

String[] digitMap = ...Array maps digit characters to their letters for quick lookup

LinkedList<String> queue = new LinkedList<>();Use linked list as queue for BFS to efficiently add/remove elements

queue.add("");Start with empty string in queue as initial combination

for (int i = 0; i < digits.length(); i++)Iterate over each digit to build combinations level by level

int size = queue.size();Store current queue size to process only existing combinations this round

String prev = queue.poll();Remove front string to extend with letters from current digit

queue.add(prev + c);Add new string with appended letter to queue

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> q;
        q.push("");
        for (char d : digits) {
            string letters = digitMap[d - '0'];
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string prev = q.front(); q.pop();
                for (char c : letters) {
                    q.push(prev + c);
                }
            }
        }
        vector<string> result;
        while (!q.empty()) {
            result.push_back(q.front());
            q.pop();
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<string> res = sol.letterCombinations("23");
    for (auto& s : res) cout << s << " ";
    cout << endl;
    return 0;
}

Line Notes

if (digits.empty()) return {};Return empty vector immediately if input is empty to avoid processing

vector<string> digitMap = {...};Map digits to corresponding letters for quick lookup

queue<string> q;Use queue to hold partial combinations for BFS

q.push("");Initialize queue with empty string as starting point

for (char d : digits)Process each digit to build combinations level by level

int size = q.size();Store current queue size to process only existing combinations this round

string prev = q.front(); q.pop();Remove front string to extend with letters from current digit

q.push(prev + c);Add new string with appended letter to queue

var letterCombinations = function(digits) {
    if (!digits.length) return [];
    const digitMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    let queue = [''];
    for (const digit of digits) {
        const letters = digitMap[digit];
        const newQueue = [];
        for (const prev of queue) {
            for (const char of letters) {
                newQueue.push(prev + char);
            }
        }
        queue = newQueue;
    }
    return queue;
};

console.log(letterCombinations('23'));

Line Notes

if (!digits.length) return [];Return empty array early if input is empty to avoid unnecessary processing

const digitMap = {...};Object maps digits to their letters for quick lookup

let queue = [''];Initialize queue with empty string as starting point

for (const digit of digits)Process each digit iteratively to build combinations level by level

const newQueue = [];Temporary array to hold new combinations for current digit

for (const prev of queue)Iterate over existing partial combinations

newQueue.push(prev + char);Append each letter to existing combinations to form new ones

queue = newQueue;Update queue with new combinations for next digit

⏱

Complexity

TimeO(4^n * n)

SpaceO(4^n * n)

Each digit can map up to 4 letters, so total combinations are up to 4^n. Each string is length n, so total space and time scale accordingly. The queue holds all partial combinations, which can be up to 4^n in number, each of length up to n.

💡 For n=3, this means up to 64 strings of length 3, so about 192 characters processed. This approach avoids recursion stack overhead by building combinations iteratively.

Interview Verdict: Accepted

This approach is iterative and avoids recursion stack overhead, useful in some interview contexts.

📊

All Approaches - One-Glance Tradeoffs

💡 Backtracking with mutable path is the best balance of clarity and efficiency and is recommended for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(4^n * n)	O(n)	Yes (deep recursion for large n)	Yes	Mention only - good for explaining basics
2. Backtracking with Mutable Path	O(4^n * n)	O(n)	Yes	Yes	Code this approach in 95% of interviews
3. Iterative Using Queue	O(4^n * n)	O(4^n * n)	No	Yes	Mention as alternative, rarely code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify input constraints and ask about empty input.State the brute force recursive approach to generate all combinations.Explain how to optimize with mutable path to reduce string creation.Mention iterative approach as an alternative to recursion.Code the approach you are most comfortable with, usually backtracking with mutable path.Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of backtracking, recursion, string building, and handling edge cases efficiently.

Common Follow-ups

• What if digits include '1' or '0'? → Handle by skipping or returning empty.
• How to handle very long input? → Discuss pruning or iterative approach.
• Can you generate combinations in lex order? → Sort or use ordered data structures.
• What if mapping changes dynamically? → Use parameterized mapping.

💡 These follow-ups test your ability to adapt the solution to variations and constraints beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Input is a string of digits or characters; 2) Need to generate all combinations or permutations; 3) Each position has multiple choices; 4) Output all possible strings.

Signature Phrases

all possible letter combinationsmapping digits to lettersreturn all combinations

NOT This Pattern When

Problems that ask for counting combinations without generating them or greedy selection problems.

Similar Problems

Generate Parentheses - backtracking to build all valid stringsPermutations - exploring all orderings of elementsCombination Sum - backtracking to find all sums

Practice

1. You need to place n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?

easy

A. Backtracking with pruning to avoid columns and diagonals already attacked

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming to count valid queen placements using subproblems

D. Breadth-first search exploring all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires placing queens so none attack each other, which involves checking columns and diagonals.

2. Step 2: Identify algorithm that prunes invalid states early

   Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking prunes invalid states early [OK]

Hint: Pruning columns and diagonals is key to efficient search [OK]

Common Mistakes:

• Thinking greedy placement always works
• Assuming DP applies directly
• Confusing BFS with pruning

2. Given the following code for generating unique permutations, what is the final output when the input is [1,1,2]?

from typing import List

def permuteUnique(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        seen = set()
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

print(permuteUnique([1,1,2]))

easy

A. [[1,2,1],[1,1,2],[2,1,1]]

B. [[1,1,2],[2,1,1],[1,2,1]]

C. [[1,1,2],[1,2,1],[2,1,1]]

D. [[2,1,1],[1,1,2],[1,2,1]]

Solution

1. Step 1: Trace initial sorting and first level of recursion

   Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.

2. Step 2: Trace subsequent recursion and skipping duplicates

   At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected unique permutations in lex order [OK]

Hint: Sort input and skip duplicates with seen set [OK]

Common Mistakes:

• Misordering output permutations due to swap order

3. Consider the following Python code implementing Heap's algorithm for permutations:

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

print(permute([1,2,3]))

What is the value of the variable res after the algorithm completes?

easy

A. [[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]]

B. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [3, 2, 1], [2, 3, 1], [1, 3, 2]]

C. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]

D. [[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [3, 2, 1], [2, 3, 1]]

Solution

1. Step 1: Trace initial state and first swaps

   Start with [1,2,3], res = [[1,2,3]]. For i=1 (odd), swap nums[c[1]] and nums[1], c[1]=0, swap nums[0] and nums[1] -> [2,1,3], append to res.

2. Step 2: Continue iterations and record permutations

   Following Heap's algorithm, the permutations generated in order are: [1,2,3], [2,1,3], [3,1,2], [1,3,2], [3,2,1], [2,3,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches Heap's algorithm output order for n=3 [OK]

Hint: Heap's algorithm generates permutations in a specific swap order [OK]

Common Mistakes:

• Confusing swap indices or order of permutations generated

4. What is the time complexity of the bitmask backtracking solution for counting all N-Queens solutions on an nxn board?

medium

A. O(n^n) because each row tries all columns independently

B. O(2^n) due to bitmask operations over all subsets of columns

C. O(n^3) from checking conflicts and iterating over rows and columns

D. O(n!) because each queen placement reduces available columns by one

Solution

1. Step 1: Identify branching factor per row

   Each row places one queen in a column not attacked by previous queens, reducing choices roughly by one each time.

2. Step 2: Calculate total recursive calls

   Thus, total calls approximate n x (n-1) x (n-2) x ... = n! permutations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking prunes invalid columns, yielding O(n!) complexity [OK]

Hint: N-Queens backtracking explores permutations -> O(n!) [OK]

Common Mistakes:

• Confusing bitmask ops with exponential subsets
• Assuming polynomial due to pruning

5. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly