Combinations (Choose K from N)

📋

Problem

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?

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

Edge cases: k = 0 → output: [[]] (empty combination)k = n → output: [[1, 2, ..., n]] (only one combination)n = 1, k = 1 → output: [[1]] (single element)

</>

IDE

def combine(n: int, k: int) -> list:public List<List<Integer>> combine(int n, int k)vector<vector<int>> combine(int n, int k)function combine(n, k)

def combine(n: int, k: int) -> list:
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> combine(int n, int k) {
    // Write your solution here
    return {};
}

function combine(n, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2],[1,3],[2,3]]Greedy approach stopping early, missing some combinations like [1,4],[2,4],[3,4].✅ Ensure recursion explores all indices from start to n, not stopping after first valid combination.

Wrong: []Missing base case for k=0, returning empty list instead of [[]].✅ Add base case: if k == 0 return [[]].

Wrong: [[1,2],[1,3]]Off-by-one error in loop bounds causing last combinations to be missed.✅ Use for i in range(start, n+1) inclusive to include all elements.

Wrong: [[1],[2],[3]]Incorrect handling of k > n, returning single elements instead of empty list.✅ Add early return [] if k > n.

Wrong: Timeout or no outputExponential time complexity without pruning or optimization.✅ Implement backtracking with pruning and start index to reduce search space.

✓

Test Cases

Focus on handling base cases and boundary inputs correctly.

Check for common pitfalls like greedy approaches and off-by-one errors.

Optimize your recursion to handle large inputs efficiently.

t1_01basic

Input{"n":4,"k":2}

Expected[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

⏱ Performance - must finish in 2000ms

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

💡 Think about generating all subsets of size k from 1 to n.

💡 Use backtracking with a start index to avoid duplicates and maintain order.

💡 When path length reaches k, add a copy of the path to results.

Why it failed: Output missing some combinations or duplicates present due to incorrect start index or no pruning. Fix by ensuring next recursion starts at i+1, not 1.

✓ Correctly generates all unique combinations of size k.

t1_02basic

Input{"n":5,"k":3}

Expected[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

⏱ Performance - must finish in 2000ms

All unique triplets from numbers 1 to 5 are listed without repetition or order differences.

💡 Extend the backtracking to select k=3 elements.

💡 Ensure each recursive call advances the start index to avoid duplicates.

💡 Add combinations to result only when path length equals k.

Why it failed: Incorrect output due to not advancing start index or adding incomplete combinations. Fix by incrementing start index in recursion and checking path length == k.

✓ Correctly lists all unique 3-element combinations.

t2_01edge

Input{"n":0,"k":0}

Expected[[]]

⏱ Performance - must finish in 2000ms

With no elements and k=0, the only combination is the empty set.

💡 Consider the base case when n=0 and k=0.

💡 The empty combination is a valid subset when k=0.

💡 Return [[]] when k=0 regardless of n.

Why it failed: Returns [] or null instead of [[]] for k=0. Fix by adding base case: if k==0 return [[]].

✓ Correctly returns the empty combination for k=0.

t2_02edge

Input{"n":1,"k":1}

Expected[[1]]

⏱ Performance - must finish in 2000ms

Single element with k=1 returns only one combination containing that element.

💡 Check behavior when n=1 and k=1.

💡 Backtracking should add the single element as the only combination.

💡 Ensure recursion handles small input sizes correctly.

Why it failed: Fails to include single element combination or returns empty list. Fix by allowing recursion to add element 1 when k=1.

✓ Correctly returns [[1]] for single element input.

t2_03edge

Input{"n":5,"k":5}

Expected[[1,2,3,4,5]]

⏱ Performance - must finish in 2000ms

When k equals n, only one combination exists: all elements from 1 to n.

💡 When k == n, the combination is the entire set from 1 to n.

💡 Backtracking should add the full path when length equals k.

💡 Check that recursion does not skip this boundary case.

Why it failed: Returns empty or partial combinations when k == n. Fix by ensuring recursion adds full path when length == k.

✓ Correctly returns the full set as the only combination.

t3_01corner

Input{"n":4,"k":3}

Expected[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

⏱ Performance - must finish in 2000ms

All unique triplets from 1 to 4, testing greedy trap where picking smallest first may miss combinations.

💡 Avoid greedy selection that stops after first valid combination.

💡 Backtracking must explore all branches, not just first found.

💡 Ensure recursion explores all indices from start to n.

Why it failed: Greedy approach returns only first few combinations, missing others. Fix by exploring all recursive branches with proper start index increments.

✓ Backtracking explores all valid combinations without greedy pruning.

t3_02corner

Input{"n":3,"k":2}

Expected[[1,2],[1,3],[2,3]]

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in loop bounds and start index handling.

💡 Check loop boundaries carefully: for i in range(start, n+1).

💡 Off-by-one errors cause missing or extra combinations.

💡 Ensure start index increments correctly to avoid duplicates.

Why it failed: Off-by-one error causes missing last element combinations. Fix loop to run up to n inclusive and increment start index properly.

✓ Loop boundaries and start index handled correctly.

t3_03corner

Input{"n":3,"k":4}

Expected[]

⏱ Performance - must finish in 2000ms

Tests handling of invalid input where k > n, expecting empty output.

💡 If k > n, no combinations possible.

💡 Add base case to return empty list when k > n.

💡 Avoid unnecessary recursion in invalid cases.

Why it failed: Returns non-empty or errors when k > n. Fix by adding early return [] if k > n.

✓ Correctly returns empty list when k > n.

t4_01performance

Input{"n":30,"k":15}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=30 and k=15; algorithm must complete within 2 seconds. Complexity is O(n choose k * k).

💡 Backtracking with pruning is required for performance.

💡 Avoid recomputation and use start index to prune search space.

💡 Iterative or DP approaches can also optimize generation.

Why it failed: Algorithm times out due to exponential complexity without pruning. Fix by implementing backtracking with start index pruning.

✓ Algorithm completes within time limit using efficient backtracking.

Practice

1. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

2. 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

3. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation

4. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities

5. Suppose the problem changes: now each element in the input array can be chosen multiple times (unlimited reuse), and duplicates still exist. Which modification to the iterative approach correctly generates all unique subsets with duplicates and unlimited reuse?

hard

A. Keep the same code but remove the duplicate skipping condition to allow reuse.

B. Sort the array, and for each element, always start from index 0 when adding new subsets to allow reuse, but skip duplicates at the same recursion level.

C. Sort the array, and for each element, start from the previous start index for duplicates, but allow reuse by appending to all existing subsets including newly added ones in the same iteration.

D. Use backtracking with a visited array to track reuse and skip duplicates by sorting.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means subsets can include the same element multiple times, so the iteration must consider all existing subsets each time.

2. Step 2: Modify iteration start index

   To allow reuse, always start from index 0 when adding new subsets, so elements can be appended multiple times. However, duplicates must still be skipped at the same recursion level to avoid repeated subsets.

3. Step 3: Confirm skipping duplicates at recursion level

   Skipping duplicates at the same recursion level prevents generating identical subsets multiple times despite reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Starting from 0 allows reuse; skipping duplicates avoids repeats [OK]

Hint: Start from 0 to allow reuse; skip duplicates at recursion level [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Starting from previous start index blocks reuse
• Using visited array unnecessarily complicates iterative approach