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 an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

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

B. Greedy algorithm that picks the largest elements first and assigns them to subsets

C. Backtracking with bitmask memoization to explore subsets and prune invalid states

D. Sorting and then using a sliding window to find equal sum partitions

Solution

1. Step 1: Understand problem constraints and complexity

   The problem requires partitioning into exactly k subsets with equal sums, which is NP-complete and requires exploring combinations exhaustively.

2. Step 2: Evaluate algorithm suitability

   Greedy and sliding window approaches fail to guarantee correctness because they don't explore all combinations. Simple DP without pruning is inefficient and incomplete. Backtracking with bitmask memoization efficiently prunes and caches states, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking with memoization handles all subsets optimally [OK]

Hint: Bitmask memoization prunes repeated subset states [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Confusing subset sum DP with partitioning into k subsets

2. The following code attempts to solve Combination Sum II but contains a subtle bug. Identify the line causing the bug.

medium

A. Line with 'if i > start and candidates[i] == candidates[i-1]: continue' for duplicate skipping

B. Line with 'if candidates[i] > target: break' for pruning

C. Line with 'backtrack(i + 1, path + [candidates[i]], target - candidates[i])' recursive call

D. Line with 'prev = candidates[i]' inside the loop

Solution

1. Step 1: Understand duplicate skipping logic

   The code uses 'if i > start and candidates[i] == candidates[i-1]: continue' to skip duplicates correctly.

2. Step 2: Identify subtle bug

   The 'prev' variable is assigned but never used, which is redundant and may confuse readers. The actual duplicate skipping is done by the index comparison, so 'prev' should be removed to avoid confusion.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Redundant 'prev' variable assignment is a subtle bug causing confusion [OK]

Hint: Duplicate skipping must be consistent and correct at recursion level; remove unused variables [OK]

Common Mistakes:

• Using prev variable incorrectly
• Skipping duplicates globally instead of per recursion level
• Not pruning when candidate > target

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

4. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes

5. If the problem changes to generating all subsets where elements can be reused unlimited times (i.e., multisets), which modification to the iterative approach correctly generates all such subsets?

hard

A. Use backtracking with recursion allowing repeated picks of the same element

B. For each num, append it to existing subsets multiple times until no new subsets are formed

C. Use the same iterative approach but iterate over nums multiple times without resetting result

D. For each num, for each subset in result, append subset + [num] and also keep subset unchanged, repeat for all nums

Solution

1. Step 1: Understand reuse requirement

   Allowing unlimited reuse means subsets can have repeated elements, unlike original subsets.

2. Step 2: Analyze iterative approach limitations

   Iterative approach as-is only adds each num once per subset; it cannot generate repeated elements subsets correctly.

3. Step 3: Identify correct approach

   Backtracking with recursion that allows repeated picks of the same element correctly generates all multisets.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking naturally supports repeated element choices [OK]

Hint: Backtracking handles repeated elements naturally [OK]

Common Mistakes:

• Trying to reuse iterative approach without modification
• Infinite loops by naive iteration
• Ignoring repeated picks in subsets