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. Given the following code to generate subsets, what is the value of result after processing num=2 when nums = [1, 2]?

easy

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

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

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

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

Solution

1. Step 1: Trace result after processing num=1

   Initially result = [[]]. After num=1, new_subsets = [[1]], result = [[], [1]].

2. Step 2: Trace result after processing num=2

   For each subset in [[], [1]], add 2: new_subsets = [[2], [1, 2]]. Extend result: [[], [1], [2], [1, 2]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All subsets of [1,2] are present exactly once [OK]

Hint: Iterative subsets double result size each iteration [OK]

Common Mistakes:

• Forgetting to add subsets with current num
• Appending duplicates
• Wrong order of subsets

2. What is the time complexity of the bitmask enumeration approach for counting the number of max bitwise-OR subsets in an array of length n?

medium

A. O(n^2)

B. O(n!)

C. O(2^n)

D. O(n * 2^n)

Solution

1. Step 1: Identify outer loop over all subsets

   There are 2^n subsets, so outer loop runs 2^n times.

2. Step 2: Identify inner loop over elements for each subset

   For each subset, we check up to n elements to compute OR, so inner loop is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   2^n subsets x n elements per subset -> O(n * 2^n) [OK]

Hint: Each subset requires checking n elements -> O(n * 2^n) [OK]

Common Mistakes:

• Confusing 2^n subsets with O(2^n) ignoring inner loop
• Assuming quadratic or factorial complexity

3. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies

4. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?

medium

A. O(n^2) because of nested loops over the array

B. O(2^n) since each element doubles the subsets

C. O(2^n * n) due to generating all subsets and copying them

D. O(n * 2^n) because sorting dominates the complexity

Solution

1. Step 1: Identify main operations affecting complexity

   Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).

2. Step 2: Calculate total time complexity

   Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Copying subsets causes the extra factor n, not just 2^n [OK]

Hint: Copying subsets adds factor n to 2^n subsets [OK]

Common Mistakes:

• Ignoring subset copying cost and saying O(2^n)
• Confusing sorting cost as dominant
• Mistaking nested loops as O(n^2)

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