Pattern #24

Combinations

Important interview questions, thinking patterns, nCr formulas, forward start index navigation, reusable vs non-reusable elements, and Go rules.

Must Solve

15 core questions — solve these first.

  1. 1.Combinations
    medium
  2. 2.Combination Sum
    medium
  3. 3.Combination Sum II
    medium
  4. 4.Combination Sum III
    medium
  5. 5.Subsets
    medium
  6. 6.Subsets II
    medium
  7. 7.Generate Parentheses
    medium
  8. 8.Letter Combinations of a Phone Number
    medium
  9. 9.Palindrome Partitioning
    medium
  10. 10.Restore IP Addresses
    medium
  11. 11.Partition Equal Subset Sum
    medium
  12. 12.Partition to K Equal Sum Subsets
    medium
  13. 13.Matchsticks to Square
    medium
  14. 14.N-Queens
    hard
  15. 15.Word Search
    medium

Also Important

8 more questions worth practicing.

  1. 16.Letter Tile Possibilities
    medium
  2. 17.Beautiful Arrangement
    medium
  3. 18.Fair Distribution of Cookies
    medium
  4. 19.Maximum Length of a Concatenated String with Unique Characters
    medium
  5. 20.Split a String Into the Max Number of Unique Substrings
    medium
  6. 21.Count Number of Maximum Bitwise-OR Subsets
    medium
  7. 22.Combination Sum IV
    medium
  8. 23.Factor Combinations
    medium

How to Think

  1. Need choose K items?Combination (nCr)
  2. Order does NOT matter?Combination ([1,2] == [2,1])
  3. Need all possible groups?Backtracking
  4. Need reach target using choices?Combination Sum
  5. Input has duplicates?Sort + skip same-level duplicates

Go Combinations Template (Choose K from N)

Standard Combinations Template in Go

func combine(n int, k int) [][]int {
    results := [][]int{}
    path := []int{}

    var dfs func(start int)
    dfs = func(start int) {
        if len(path) == k {
            copyPath := append([]int(nil), path...)
            results = append(results, copyPath)
            return
        }

        // Optimization Pruning: Stop if remaining elements (n - i + 1) < needed (k - len(path))
        for i := start; i <= n - (k - len(path)) + 1; i++ {
            path = append(path, i)
            dfs(i + 1) // Move start forward strictly to avoid reversed duplicates like [2, 1]
            path = path[:len(path)-1] // Undo
        }
    }

    dfs(1)
    return results
}

👉 Total Time: O(K × nCk) | Space: O(K) (Recursion depth = K)

Reusable vs Non-Reusable Elements

Cannot Reuse Elements (dfs(i + 1))
dfs(i + 1)  // Move start to next index!

Used for standard Combinations and Combination Sum II where each number can be picked at most once.

Can Reuse Elements (dfs(i))
dfs(i)  // Keep start index at current i!

Used for Combination Sum I where the same number can be chosen an unlimited number of times!

Pruning Optimizations

Pruning stops exploring impossible recursion branches early before wasting CPU cycles:

1. Target Exceeded

If all numbers are positive and sum > target, stop recursion immediately!

2. Insufficient Remaining Elements

If remaining elements (n - i + 1) < (k - len(path)), stop loop because it is impossible to reach size K!

Visual Memory Rule
Order Does NOT Matter! → [1, 2] == [2, 1] (Use start index to avoid reverse duplicates)
Reuse Elements?        → Call dfs(i)
Single-Use Elements?   → Call dfs(i + 1)
Prune Invalid Branch   → Stop if sum > target or remaining elements < needed

💡 Golden Rule: "Choose an item, move forward, and never generate the same group in a different order."

Common Interview Mistakes

1. Generating Permutations Instead

Generating both [1, 2] and [2, 1] for combinations. Always use start index to move forward strictly!

2. Wrong Next Index

Passing dfs(i + 1) when element reuse is allowed, or passing dfs(i) when element reuse is prohibited.

3. Forgetting Undo

Adding item to path but forgetting path = path[:len(path)-1] pops state after recursion returns.

4. Not Copying Path in Go

Saving path without copy causes later backtracking pops to mutate saved combination results!

Interview Rules

  1. 1. Choose K items? → Combinations (nCr)
  2. 2. Order does NOT matter? → Combination ([1, 2] == [2, 1])
  3. 3. Move forward strictly → start index avoids reversed duplicates
  4. 4. Cannot reuse elements? → Recurse with i + 1
  5. 5. Can reuse elements? → Recurse with i
  6. 6. Target sum reached? → Save answer
  7. 7. Duplicate input? → Sort first + skip same-level duplicates
  8. 8. Overall Complexity → O(K × nCk) time, O(K) space

Small Rules

  1. Rule 1: Order does not matter in combinations.
  2. Rule 2: Use start index to avoid generating reversed duplicate groups.
  3. Rule 3: Base case for choosing K items is len(path) == k.
  4. Rule 4: Base case for target sum is sum == target.
  5. Rule 5:Stop branch early if remaining elements (n - i + 1) < needed (k - len(path)).

Production Thinking

Incident Response Team Building → Choose 3 engineers from 10 (Order doesn't matter) = 10C3 = 120 team combinations

Feature Variant Selection → Select exactly 3 features out of 10 for A/B testing experiment group

Replica Server Selection → Choose 3 replica nodes out of 20 available server instances

Test Configuration Groups → Test every combination group of 2 enabled feature flags across system

Production Warning → Combination growth: Choosing 10 from 20 = 20C10 = 184,756 combinations! Prune and constrain production searches.

Remember This

Combination           → Order does NOT matter
Choose K              → Backtracking
Avoid reversed dups   → Start index
Cannot reuse          → i + 1
Can reuse             → i
Duplicates            → Sort + skip same level
Target reached        → Save
Impossible            → Prune

💡 Golden Rule: "Choose an item, move forward, and never generate the same group in a different order."