Combinations (Choose K from N)

🎯

Combinations (Choose K from N)

mediumBACKTRACKINGAmazonGoogle

Imagine you are organizing a team-building event and need to select exactly k members from a group of n people. How many unique ways can you form such a team?

💡 This problem asks for all unique combinations of k elements chosen from n distinct elements. Beginners often struggle because they confuse combinations with permutations and find it tricky to avoid duplicates or manage the recursive calls properly.

📋

Problem Statement

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. Each combination should be a unique set of numbers, and the order of combinations does not matter.

1 ≤ n ≤ 301 ≤ k ≤ n

💡

Example

Input"n = 4, k = 2"

Output[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

All unique pairs from numbers 1 to 4 are listed without repetition or order differences.

• k = 0 → output: [[]] (empty combination)
• k = n → output: [[1, 2, ..., n]] (only one combination)
• n = 1, k = 1 → output: [[1]] (single element)
• k > n → output: [] (no valid combinations)

⚠️

Common Mistakes

Not backtracking (not removing last element after recursion)

Results contain incorrect or duplicate combinations

✅ Always pop/remove the last element after recursive call

Starting recursion from 0 instead of 1 or wrong start index

Combinations include invalid numbers or duplicates

✅ Start from 1 and increment start index properly to avoid duplicates

Appending path directly instead of a copy

All results end up the same due to reference sharing

✅ Append a copy of the current path (e.g., path[:], new ArrayList<>(path))

Not handling edge cases like k=0 or k>n

Code may crash or return incorrect results

✅ Add checks for edge cases and return appropriate results

Confusing combinations with permutations

Output includes duplicates or wrong orderings

✅ Ensure order is non-decreasing and start index increments to avoid permutations

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive nature and the combinatorial explosion, even though it's not efficient for large inputs.

Intuition

Try every possible combination by recursively choosing or skipping each number, building combinations until the size k is reached.

Algorithm

1. Start from number 1 and try to include it in the current combination.
2. Recursively proceed to the next number, adding it if the combination size is less than k.
3. If the combination size reaches k, add it to the results.
4. Backtrack by removing the last added number and try the next possibility.

💡 The challenge is to manage the recursion and backtracking correctly so that all unique combinations are generated without duplicates.

</>

Code

from typing import List

def combine(n: int, k: int) -> List[List[int]]:
    result = []
    def backtrack(start: int, path: List[int]):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

# Example usage
if __name__ == '__main__':
    print(combine(4, 2))

Line Notes

def combine(n: int, k: int) -> List[List[int]]:Defines the function signature with input and output types for clarity.

def backtrack(start: int, path: List[int]):Helper function to build combinations starting from 'start' index.

if len(path) == k:Base case: when current combination size equals k, add a copy to results.

for i in range(start, n + 1):Iterate over remaining numbers to include in the combination.

path.append(i)Choose the current number and add it to the current path.

backtrack(i + 1, path)Recurse with next starting number to avoid duplicates and maintain order.

path.pop()Backtrack by removing the last number to explore other possibilities.

return resultReturn all collected combinations after recursion completes.

import java.util.*;

public class Combinations {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            backtrack(i + 1, n, k, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
    }
}

Line Notes

public static List<List<Integer>> combine(int n, int k) {Main function to initiate combination generation.

backtrack(1, n, k, new ArrayList<>(), result);Start recursion from number 1 with empty path.

if (path.size() == k) {Base case: when combination size reaches k, add a copy to results.

for (int i = start; i <= n; i++) {Loop through numbers from start to n to build combinations.

path.add(i);Choose current number to include in combination.

backtrack(i + 1, n, k, path, result);Recurse with next number to avoid duplicates.

path.remove(path.size() - 1);Backtrack by removing last number to try other options.

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

class Solution {
public:
    void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            backtrack(i + 1, n, k, path, result);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(1, n, k, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> res = sol.combine(4, 2);
    for (auto& comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i < comb.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {Recursive helper to build combinations starting from 'start'.

if (path.size() == k) {Base case: when combination size equals k, add to results.

for (int i = start; i <= n; i++) {Iterate over remaining numbers to include in combination.

path.push_back(i);Include current number in the path.

backtrack(i + 1, n, k, path, result);Recurse with next number to avoid duplicates.

path.pop_back();Backtrack by removing last number to explore other options.

vector<vector<int>> combine(int n, int k) {Main function to start recursion and return results.

function combine(n, k) {
    const result = [];
    function backtrack(start, path) {
        if (path.length === k) {
            result.push([...path]);
            return;
        }
        for (let i = start; i <= n; i++) {
            path.push(i);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(1, []);
    return result;
}

// Example usage
console.log(combine(4, 2));

Line Notes

function combine(n, k) {Defines main function to generate combinations.

function backtrack(start, path) {Helper recursive function to build combinations.

if (path.length === k) {Base case: when combination size reaches k, add a copy to results.

for (let i = start; i <= n; i++) {Loop through numbers from start to n to build combinations.

path.push(i);Choose current number to include in combination.

backtrack(i + 1, path);Recurse with next number to avoid duplicates.

path.pop();Backtrack by removing last number to try other options.

⏱

Complexity

TimeO(n choose k * k)

SpaceO(k) for recursion stack + O(n choose k * k) for output

We explore all combinations of size k from n elements, which is n choose k. Each combination takes O(k) to copy into results.

💡 For n=20 and k=10, this means exploring about 184,756 combinations, which is large but manageable for medium constraints.

Interview Verdict: Accepted

This approach works well for moderate n and k, but can be slow for very large inputs due to combinatorial explosion.

🧠

Backtracking with Pruning

💡 This approach improves brute force by pruning branches early when it's impossible to reach k elements, saving unnecessary recursion.

Intuition

If the remaining numbers are fewer than needed to complete the combination, stop exploring that path.

Algorithm

1. Start from number 1 and try to include it in the current combination.
2. Before recursing, check if enough numbers remain to complete the combination.
3. If not enough numbers remain, backtrack immediately.
4. Otherwise, recurse and backtrack as usual.

💡 Pruning reduces the search space significantly, especially when k is close to n.

</>

Code

from typing import List

def combine(n: int, k: int) -> List[List[int]]:
    result = []
    def backtrack(start: int, path: List[int]):
        if len(path) == k:
            result.append(path[:])
            return
        # Prune if not enough elements remain
        if len(path) + (n - start + 1) < k:
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return result

# Example usage
if __name__ == '__main__':
    print(combine(4, 2))

Line Notes

def combine(n: int, k: int) -> List[List[int]]:Defines the function signature with input and output types for clarity.

def backtrack(start: int, path: List[int]):Recursive helper with pruning logic.

if len(path) == k:Base case: when combination size reaches k, add a copy to results.

if len(path) + (n - start + 1) < k:Prune recursion if remaining numbers can't fill combination.

for i in range(start, n + 1):Iterate over candidates starting from 'start'.

path.append(i)Choose current number to include.

backtrack(i + 1, path)Recurse with next number.

path.pop()Backtrack to explore other options.

import java.util.*;

public class Combinations {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (path.size() + (n - start + 1) < k) {
            return; // prune
        }
        for (int i = start; i <= n; i++) {
            path.add(i);
            backtrack(i + 1, n, k, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
    }
}

Line Notes

public static List<List<Integer>> combine(int n, int k) {Main function to initiate combination generation.

private static void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {Recursive helper with pruning.

if (path.size() == k) {Base case: when combination size reaches k, add a copy to results.

if (path.size() + (n - start + 1) < k) {Prune recursion when not enough elements remain to complete combination.

for (int i = start; i <= n; i++) {Loop over candidates starting from 'start'.

path.add(i);Include current number.

backtrack(i + 1, n, k, path, result);Recurse with next number.

path.remove(path.size() - 1);Backtrack to try other options.

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

class Solution {
public:
    void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        if (path.size() + (n - start + 1) < k) {
            return; // prune
        }
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            backtrack(i + 1, n, k, path, result);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(1, n, k, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> res = sol.combine(4, 2);
    for (auto& comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i < comb.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

class Solution {Class encapsulating the solution methods.

void backtrack(int start, int n, int k, vector<int>& path, vector<vector<int>>& result) {Recursive helper with pruning.

if (path.size() == k) {Base case: when combination size equals k, add to results.

if (path.size() + (n - start + 1) < k) {Prune recursion when not enough elements remain to complete combination.

for (int i = start; i <= n; i++) {Loop over candidates starting from 'start'.

path.push_back(i);Include current number.

backtrack(i + 1, n, k, path, result);Recurse with next number.

path.pop_back();Backtrack to try other options.

function combine(n, k) {
    const result = [];
    function backtrack(start, path) {
        if (path.length === k) {
            result.push([...path]);
            return;
        }
        if (path.length + (n - start + 1) < k) {
            return; // prune
        }
        for (let i = start; i <= n; i++) {
            path.push(i);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(1, []);
    return result;
}

console.log(combine(4, 2));

Line Notes

function combine(n, k) {Defines main function to generate combinations.

function backtrack(start, path) {Recursive helper with pruning.

if (path.length === k) {Base case: when combination size reaches k, add a copy to results.

if (path.length + (n - start + 1) < k) {Prune recursion when not enough elements remain to complete combination.

for (let i = start; i <= n; i++) {Loop over candidates starting from 'start'.

path.push(i);Include current number.

backtrack(i + 1, path);Recurse with next number.

path.pop();Backtrack to try other options.

⏱

Complexity

TimeO(n choose k * k)

SpaceO(k) recursion stack + O(n choose k * k) output

Pruning reduces some recursion calls but worst-case remains combinatorial.

💡 Pruning helps especially when k is close to n, reducing unnecessary exploration.

Interview Verdict: Accepted

This is a practical improvement over brute force, often expected in interviews to show optimization skills.

🧠

Iterative Combinations Generation (Lexicographic Order)

💡 This approach uses an iterative method to generate combinations in lex order, avoiding recursion and stack overhead.

Intuition

Start with the smallest combination and repeatedly generate the next combination by incrementing elements from right to left.

Algorithm

1. Initialize the first combination as [1, 2, ..., k].
2. Add the current combination to results.
3. Find the rightmost element that can be incremented without exceeding n.
4. Increment that element and reset all elements to its right accordingly.
5. Repeat until no more increments are possible.

💡 This method systematically enumerates all combinations without recursion, which can be easier to debug and faster in some languages.

</>

Code

from typing import List

def combine(n: int, k: int) -> List[List[int]]:
    result = []
    comb = list(range(1, k + 1))
    while True:
        result.append(comb[:])
        # Find the rightmost element to increment
        i = k - 1
        while i >= 0 and comb[i] == n - k + i + 1:
            i -= 1
        if i < 0:
            break
        comb[i] += 1
        for j in range(i + 1, k):
            comb[j] = comb[j - 1] + 1
    return result

# Example usage
if __name__ == '__main__':
    print(combine(4, 2))

Line Notes

def combine(n: int, k: int) -> List[List[int]]:Defines the function signature with input and output types for clarity.

comb = list(range(1, k + 1))Initialize first combination as smallest lex order.

while True:Loop until all combinations are generated.

result.append(comb[:])Add current combination copy to results.

i = k - 1Start from the last element to find increment position.

while i >= 0 and comb[i] == n - k + i + 1:Find element that can be incremented without overflow.

if i < 0:If none found, all combinations generated.

comb[i] += 1Increment the found element.

for j in range(i + 1, k):Reset elements to the right to maintain increasing order.

import java.util.*;

public class Combinations {
    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int[] comb = new int[k];
        for (int i = 0; i < k; i++) {
            comb[i] = i + 1;
        }
        while (true) {
            List<Integer> current = new ArrayList<>();
            for (int x : comb) current.add(x);
            result.add(current);
            int i = k - 1;
            while (i >= 0 && comb[i] == n - k + i + 1) {
                i--;
            }
            if (i < 0) break;
            comb[i]++;
            for (int j = i + 1; j < k; j++) {
                comb[j] = comb[j - 1] + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(combine(4, 2));
    }
}

Line Notes

public static List<List<Integer>> combine(int n, int k) {Main function to initiate combination generation.

int[] comb = new int[k];Initialize array to hold current combination.

for (int i = 0; i < k; i++) { comb[i] = i + 1; }Set first combination to smallest lex order.

while (true) {Loop to generate all combinations.

List<Integer> current = new ArrayList<>();Create list to store current combination.

for (int x : comb) current.add(x);Copy current combination to list.

result.add(current);Add current combination to results.

int i = k - 1;Start from last element to find increment position.

while (i >= 0 && comb[i] == n - k + i + 1) { i--; }Find element that can be incremented.

if (i < 0) break;No more combinations if none can be incremented.

comb[i]++;Increment element at position i.

for (int j = i + 1; j < k; j++) { comb[j] = comb[j - 1] + 1; }Reset elements to the right.

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

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> comb(k);
        for (int i = 0; i < k; i++) comb[i] = i + 1;
        while (true) {
            result.push_back(comb);
            int i = k - 1;
            while (i >= 0 && comb[i] == n - k + i + 1) i--;
            if (i < 0) break;
            comb[i]++;
            for (int j = i + 1; j < k; j++) {
                comb[j] = comb[j - 1] + 1;
            }
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> res = sol.combine(4, 2);
    for (auto& comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i < comb.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

class Solution {Class encapsulating the solution methods.

vector<vector<int>> combine(int n, int k) {Main function to generate combinations iteratively.

vector<int> comb(k);Initialize vector to hold current combination.

for (int i = 0; i < k; i++) comb[i] = i + 1;Set first combination to smallest lex order.

while (true) {Loop to generate all combinations.

result.push_back(comb);Add current combination to results.

int i = k - 1;Start from last element to find increment position.

while (i >= 0 && comb[i] == n - k + i + 1) i--;Find element that can be incremented.

if (i < 0) break;No more combinations if none can be incremented.

comb[i]++;Increment element at position i.

for (int j = i + 1; j < k; j++) { comb[j] = comb[j - 1] + 1; }Reset elements to the right.

function combine(n, k) {
    const result = [];
    const comb = Array.from({length: k}, (_, i) => i + 1);
    while (true) {
        result.push(comb.slice());
        let i = k - 1;
        while (i >= 0 && comb[i] === n - k + i + 1) {
            i--;
        }
        if (i < 0) break;
        comb[i]++;
        for (let j = i + 1; j < k; j++) {
            comb[j] = comb[j - 1] + 1;
        }
    }
    return result;
}

console.log(combine(4, 2));

Line Notes

function combine(n, k) {Defines main function to generate combinations.

const comb = Array.from({length: k}, (_, i) => i + 1);Initialize first combination in lex order.

while (true) {Loop to generate all combinations.

result.push(comb.slice());Add current combination copy to results.

let i = k - 1;Start from last element to find increment position.

while (i >= 0 && comb[i] === n - k + i + 1) { i--; }Find element that can be incremented.

if (i < 0) break;Stop if no element can be incremented.

comb[i]++;Increment element at position i.

for (let j = i + 1; j < k; j++) { comb[j] = comb[j - 1] + 1; }Reset elements to the right.

⏱

Complexity

TimeO(n choose k * k)

SpaceO(k) for current combination + O(n choose k * k) for output

Each combination is generated in lex order with O(k) work per combination.

💡 This iterative approach avoids recursion overhead and is efficient for moderate n and k.

Interview Verdict: Accepted

This approach is a good alternative to recursion and shows mastery of combinatorial generation techniques.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the backtracking with pruning approach is ideal as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n choose k * k)	O(k) recursion + O(n choose k * k) output	Yes (deep recursion for large n)	Yes	Mention only - never code unless asked
2. Backtracking with Pruning	O(n choose k * k) but fewer calls	O(k) recursion + O(n choose k * k) output	Less risk due to pruning	Yes	Code this approach in 95% of interviews
3. Iterative Lexicographic	O(n choose k * k)	O(k) + output	No	Yes	Mention as alternative; code if recursion not allowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize with pruning, and finally mention iterative solutions if time permits.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force recursive approach to generate all combinations.Explain pruning to optimize recursion and reduce unnecessary calls.Mention iterative lexicographic generation as an alternative.Code the chosen approach carefully and test with edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your understanding of recursion, backtracking, pruning, and combinatorial generation. They also assess your ability to optimize and write clean code.

Common Follow-ups

• What if the input array is not 1..n but an arbitrary list? → Use backtracking with start index on the array.
• How to handle duplicates in input? → Sort and skip duplicates during recursion.

💡 These follow-ups test your ability to adapt the solution to variations and handle duplicates, common in real interviews.

🔍

Pattern Recognition

When to Use

1) Asked to generate all subsets/combinations of fixed size k; 2) Input is a range or array; 3) Order of elements in combination does not matter; 4) Need unique combinations without duplicates.

Signature Phrases

choose k from nall possible combinationsunique sets of size k

NOT This Pattern When

Problems asking for permutations or subsets with duplicates handled differently

Similar Problems

Subsets - generates all subsets of any size, this problem fixes size kCombination Sum - similar backtracking but with sum constraints and repeated elementsPermutations - order matters, unlike combinations

Practice

1. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

2. What is the time complexity of the backtracking solution with frequency counting for the Combination Sum (Reuse Allowed) problem, where N is the number of candidates, T is the target, and M is the minimum candidate value?

medium

A. O(N * T) because each candidate is tried once for each target value.

B. O(2^N) because each candidate can be either included or excluded once.

C. O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M.

D. O(T^N) because for each target value, all candidates are tried in all combinations.

Solution

1. Step 1: Identify recursion depth and branching factor

   The recursion depth is roughly T/M because the smallest candidate can be used up to T/M times. At each level, up to N candidates are considered with multiple counts.

2. Step 2: Calculate total number of recursive calls

   Each candidate can be chosen 0 to max_use times, leading to branching factor roughly N^(T/M + 1). This exponential complexity dominates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exponential branching with depth proportional to T/M matches O(N^(T/M + 1)) because the recursion tree branches exponentially with depth proportional to T/M. [OK]

Hint: Exponential in target divided by smallest candidate [OK]

Common Mistakes:

• Confusing DP complexity with backtracking
• Ignoring exponential branching due to reuse

3. What is the time complexity of the optimal backtracking with bitmask and memoization solution for the Matchsticks to Square problem, where n is the number of matchsticks?

medium

A. O(4^n) because each stick can go to one of four sides

B. O(n * 2^n) due to exploring subsets with bitmask and pruning repeated states

C. O(n^2) because of sorting and nested loops

D. O(2^n) ignoring the linear factor from iterating over sticks

Solution

1. Step 1: Identify state space size

   The algorithm explores subsets represented by bitmasks, so there are 2^n states.

2. Step 2: Consider per-state work

   For each state, it iterates over n sticks to try adding one stick, leading to O(n * 2^n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask states times linear iteration per state [OK]

Hint: Bitmask states times linear iteration per state [OK]

Common Mistakes:

• Confusing 4^n with 2^n
• Ignoring linear factor n
• Assuming sorting dominates complexity

4. The following code attempts to solve the Matchsticks to Square problem using backtracking with bitmask and memoization. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line with 'if total % 4 != 0: return false' (no divisibility check)

B. Line with 'matchsticks.sort(reverse=true)' (missing sorting causes inefficiency)

C. Line with 'memo[(used_mask, curr_sum, sides_formed)] = false' (incorrect memoization)

D. Line with recursive call 'backtrack(next_mask, next_sum, sides_formed)' missing return statement

Solution

1. Step 1: Identify missing return in recursion

   The recursive call without return means the function ignores successful paths, causing incorrect results or infinite recursion.

2. Step 2: Confirm other lines are correct

   Divisibility check is present, sorting is done, and memoization line is correct for caching failures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing return in recursive call breaks backtracking correctness [OK]

Hint: Missing return in recursive call breaks correctness [OK]

Common Mistakes:

• Forgetting to return recursive call result
• Skipping divisibility check
• Not sorting before backtracking

5. Suppose the Matchsticks to Square problem is modified so that each matchstick can be used multiple times (unlimited reuse). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use backtracking without bitmask, allowing repeated selection of sticks, and prune when side length exceeded.

B. Keep the bitmask to track used sticks but allow multiple bits per stick to represent reuse counts.

C. Remove the bitmask and use a classic unbounded knapsack DP to check if four sides can be formed from unlimited sticks.

D. Sort sticks and greedily assign sticks to sides repeatedly until all sides are formed.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means the problem becomes an unbounded partition problem, not a subset partition.

2. Step 2: Identify suitable algorithm

   Bitmask tracking used sticks is invalid since sticks can be reused infinitely. Backtracking without bitmask is inefficient. Greedy fails due to partition constraints. Unbounded knapsack DP correctly models unlimited usage.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Unbounded knapsack fits unlimited reuse scenario [OK]

Hint: Unbounded knapsack fits unlimited reuse scenario [OK]

Common Mistakes:

• Trying to track usage with bitmask for unlimited reuse
• Using greedy for partitioning
• Ignoring pruning in backtracking