Data Structures & AlgorithmsBacktracking — Systematic Exploration

Permutations & Combinations

LevelIntermediate

Duration90 mins

TopicBacktracking — Systematic Exploration

2 / 4

Generating K-Combinations

The Art of Selection Without Arrangement

While permutations answer "in how many ways can we arrange elements?", combinations answer a fundamentally different question: "in how many ways can we select elements?" The distinction is subtle but profound. When forming a committee of 3 from 10 candidates, the order of selection doesn't matter—{Alice, Bob, Carol} is the same committee as {Carol, Alice, Bob}. This is a combination problem.

A k-combination (or simply "combination of size k") is an unordered selection of k elements from a set of n elements. Unlike permutations, where [1,2,3] and [2,1,3] are distinct, in combinations, {1,2,3} is the single way to choose these three elements.

The number of k-combinations from n elements is denoted C(n,k) or "n choose k" (written as ⁿCₖ or (ⁿₖ)), computed as n! / (k! × (n-k)!). This grows much slower than n!, making exhaustive combination generation feasible for larger problem sizes than permutation generation.

What You Will Master

By the end of this page, you will deeply understand:

• The mathematical relationship between combinations and permutations • Why backtracking with ordered selection avoids duplicates • Multiple implementation strategies with their tradeoffs • How to adapt the combination template for variant problems • Complexity analysis and practical performance considerations

Mathematical Foundations of Combinations

Understanding the mathematical structure of combinations is essential for understanding why certain algorithmic choices lead to correct and efficient implementations.

Formal Definition:

A k-combination of a set S = {a₁, a₂, ..., aₙ} is a subset of S containing exactly k elements. Since sets are unordered, {1,2,3} and {3,1,2} represent the same combination.

The Binomial Coefficient:

The number of k-combinations from n elements is given by the binomial coefficient:

C(n, k) = n! / (k! × (n-k)!)

This formula has an elegant interpretation:

n! counts all permutations of choosing k elements from n
But since order doesn't matter in combinations, we divide by k! (the number of ways to arrange k chosen elements)
The (n-k)! in the denominator comes from the original factorial formula

Alternative Formula

The binomial coefficient can also be computed as:

C(n, k) = [n × (n-1) × ... × (n-k+1)] / [k × (k-1) × ... × 1]

This form avoids computing large factorials and is numerically more stable for implementation.

Combination Counts: C(n, k) for Various n and k
n \ k	1	2	3	4	5	10	n/2
5	5	10	10	5	1		10
10	10	45	120	210	252	1	252
20	20	190	1,140	4,845	15,504	184,756	184,756
30	30	435	4,060	27,405	142,506	30,045,015	155,117,520
50	50	1,225	19,600	230,300	2,118,760	~10 billion	~126 trillion

Key Observations:

Symmetry: C(n, k) = C(n, n-k). Choosing k elements to include is equivalent to choosing (n-k) elements to exclude.
Maximum at the middle: C(n, k) reaches its maximum when k = n/2 (or nearest integers for odd n). This is where combination counts explode.
Much smaller than factorials: Compare C(20, 10) ≈ 184,756 with 20! ≈ 2.4 × 10¹⁸. Combinations are vastly more tractable than permutations for complete enumeration.
Pascal's Identity: C(n, k) = C(n-1, k-1) + C(n-1, k). This recursive relationship is the foundation of the backtracking approach.

Pascal's Identity Intuition:

Consider element aₙ. In any k-combination, either:

aₙ is included: then we need to choose k-1 elements from the remaining n-1 → C(n-1, k-1) ways
aₙ is excluded: then we need to choose k elements from the remaining n-1 → C(n-1, k) ways

Total: C(n-1, k-1) + C(n-1, k) = C(n, k)

Properties of Combinations

•Unordered Selection: Order of elements doesn't matter; {1,2,3} = {3,2,1}
•No Repetition: Each element appears at most once in a combination
•Subset Relationship: Each k-combination is a k-element subset of the original set
•Cardinality: Exactly C(n,k) distinct k-combinations exist
•Sum of All: C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ (total subsets)

The Backtracking Paradigm for Combinations

Generating combinations through backtracking requires a subtle but crucial modification compared to permutations. The key insight is that we must enforce an ordering constraint to avoid generating the same combination multiple times.

The Duplicate Problem:

If we simply try all ways to add k elements to our current combination (as we do for permutations), we'll generate duplicates:

Selecting 2 from [1,2,3]:
- Choose 1, then choose 2 → {1,2}
- Choose 2, then choose 1 → {2,1} = {1,2} (duplicate!)

The Solution: Ordered Selection

We only consider elements that come after the last element we chose. This ensures each combination is generated exactly once, with elements in increasing order:

Selecting 2 from [1,2,3]:
- Start at index 0, choose 1:
  - Consider indices > 0: choose 2 → {1,2}
  - Consider indices > 0: choose 3 → {1,3}
- Start at index 1, choose 2:
  - Consider indices > 1: choose 3 → {2,3}
- Start at index 2, choose 3:
  - No valid second element (need index > 2)

Result: {1,2}, {1,3}, {2,3} — exactly C(3,2) = 3 combinations, no duplicates.

The Canonical Form Principle

By always producing combinations with elements in sorted order, we define a canonical form for each combination. Since the elements within any combination can be sorted uniquely, we ensure each combination is generated exactly once in its canonical (sorted) form. This is a powerful pattern that extends to many combinatorial generation problems.

The Decision Tree Structure:

For selecting 2 elements from [1, 2, 3, 4], the decision tree looks like:

                        [start]
                    /    |    \    \
                   1     2     3    4      ← First element (start index)
                /|\    /\    |
               2 3 4   3 4   4              ← Second element (index > first)

Each root-to-leaf path of length 2 represents a valid 2-combination. Notice:

After choosing 1, we can choose 2, 3, or 4
After choosing 2, we can only choose 3 or 4 (not 1, as that would duplicate {1,2})
After choosing 3, only 4 remains
After choosing 4, no valid second element exists at higher indices

The Backtracking Invariant:

At any point in the recursion:

current holds a combination prefix with elements in increasing order
startIndex indicates the minimum index from which to select the next element
All elements in current have indices less than startIndex

Backtracking Invariants for Combinations

•Ordering Constraint: Elements in current are always in ascending order (by original index)
•Suffix Selection: We only select from elements[startIndex:] to avoid revisiting earlier elements
•Size Bound: We stop adding elements when current.length === k
•Exhaustiveness: At each position, we try all valid choices (all indices from startIndex to n-1)
•No Repetition: Each element index can appear at most once in current

The Classic Implementation

The standard backtracking implementation for k-combinations uses a startIndex parameter to enforce the ordering constraint. This elegant approach requires no auxiliary data structures beyond the recursion itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function generateCombinations<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    function backtrack(startIndex: number): void {
        // Base case: combination complete
        if (current.length === k) {
            results.push([...current]); // Copy to avoid mutation
            return;
        }
        
        // Pruning: not enough elements left to complete combination
        const remaining = k - current.length;
        const available = n - startIndex;
        if (available < remaining) return; // Early termination
        
        // Try each element from startIndex onwards
        for (let i = startIndex; i < n; i++) {
            // Choose: add element to current combination
            current.push(elements[i]);
            
            // Explore: recurse with next starting position
            backtrack(i + 1); // Note: i + 1, not startIndex + 1
            
            // Unchoose: remove element for next iteration
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
// Example usage
console.log("C(4, 2) - All 2-combinations of [1,2,3,4]:");
generateCombinations([1, 2, 3, 4], 2).forEach(c => console.log(c));
 
// Output:
// [1, 2]
// [1, 3]
// [1, 4]
// [2, 3]
// [2, 4]
// [3, 4]
 
console.log("\nC(5, 3) - All 3-combinations of ['a','b','c','d','e']:");
generateCombinations(['a', 'b', 'c', 'd', 'e'], 3).forEach(c => console.log(c.join("")));

Execution Trace for C(4, 2):

backtrack(0), current=[]
  i=0: choose 1 → current=[1]
    backtrack(1), current=[1]
      i=1: choose 2 → current=[1,2], length=k → RECORD [1,2]
           unchoose 2 → current=[1]
      i=2: choose 3 → current=[1,3], length=k → RECORD [1,3]
           unchoose 3 → current=[1]
      i=3: choose 4 → current=[1,4], length=k → RECORD [1,4]
           unchoose 4 → current=[1]
    return
  unchoose 1 → current=[]
  i=1: choose 2 → current=[2]
    backtrack(2), current=[2]
      i=2: choose 3 → current=[2,3], length=k → RECORD [2,3]
      i=3: choose 4 → current=[2,4], length=k → RECORD [2,4]
    return
  i=2: choose 3 → current=[3]
    backtrack(3), current=[3]
      i=3: choose 4 → current=[3,4], length=k → RECORD [3,4]
  i=3: choose 4 → current=[4]
    backtrack(4), available=0 < remaining=1 → PRUNE (return)

Notice the pruning on the last iteration: we can't form a 2-combination starting with just element at index 3.

The Critical 'i + 1' Detail

When recursing, we pass i + 1 (not startIndex + 1). This ensures we only consider elements after the one we just chose. If we passed startIndex + 1, we'd reconsider the same elements at each level, leading to duplicates.

Complexity Analysis:

Time Complexity: O(k × C(n, k))

We generate C(n, k) combinations
Each combination requires O(k) work to copy into results
The recursion tree has O(C(n, k)) leaves plus internal nodes, but the total work is dominated by output generation

Space Complexity: O(k) for the recursion (excluding output)

current array: O(k)
Recursion stack depth: O(k)
Output storage: O(k × C(n, k))

Per-Combination Overhead: O(k) for copying the result array.

The Pruning Optimization:

The early termination check is crucial for efficiency:

const remaining = k - current.length;
const available = n - startIndex;
if (available < remaining) return;

Without this pruning, we'd explore many branches that can never yield complete combinations. For example, trying to form a 10-combination starting from position 995 in a 1000-element array is futile—we'd have at most 5 elements available.

The Include/Exclude Decision Paradigm

An alternative perspective on combination generation uses a binary include/exclude decision for each element. Instead of asking "which element do I add next?", we ask "do I include this specific element or not?"

This approach mirrors Pascal's Identity: C(n, k) = C(n-1, k-1) + C(n-1, k)

Include element n: reduces to choosing k-1 from remaining n-1
Exclude element n: reduces to choosing k from remaining n-1

Conceptual Model:

We process elements one by one (e.g., left to right). For each element, we branch:

Left branch: Include this element in the combination
Right branch: Exclude this element from the combination

Base cases:

If we've included k elements, we have a complete combination
If we've processed all elements without reaching k, this branch fails
If remaining elements can't possibly complete the combination, prune

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function combinationsIncludeExclude<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    function backtrack(index: number): void {
        // Base case: combination complete
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Base case: processed all elements without completing
        if (index === n) return;
        
        // Pruning: not enough elements left
        const remaining = k - current.length;
        const available = n - index;
        if (available < remaining) return;
        
        // Branch 1: INCLUDE elements[index]
        current.push(elements[index]);
        backtrack(index + 1);
        current.pop();
        
        // Branch 2: EXCLUDE elements[index]
        backtrack(index + 1);
    }
    
    backtrack(0);
    return results;
}
 
// Trace version for understanding
function combinationsWithTrace<T>(elements: T[], k: number): void {
    const current: T[] = [];
    const indent = (d: number) => "  ".repeat(d);
    
    function backtrack(index: number, depth: number): void {
        console.log(`${indent(depth)}backtrack(index=${index}), current=[${current}]`);
        
        if (current.length === k) {
            console.log(`${indent(depth)}→ RECORD: [${current}]`);
            return;
        }
        if (index === elements.length) {
            console.log(`${indent(depth)}→ End of elements, incomplete`);
            return;
        }
        
        // Include
        console.log(`${indent(depth)}Include ${elements[index]}`);
        current.push(elements[index]);
        backtrack(index + 1, depth + 1);
        current.pop();
        
        // Exclude
        console.log(`${indent(depth)}Exclude ${elements[index]}`);
        backtrack(index + 1, depth + 1);
    }
    
    backtrack(0, 0);
}
 
console.log("Include/Exclude trace for C(3, 2):");
combinationsWithTrace([1, 2, 3], 2);

Trace Output:

backtrack(index=0), current=[]
Include 1
  backtrack(index=1), current=[1]
  Include 2
    backtrack(index=2), current=[1,2]
    → RECORD: [1,2]
  Exclude 2
    backtrack(index=2), current=[1]
    Include 3
      backtrack(index=3), current=[1,3]
      → RECORD: [1,3]
    Exclude 3
      backtrack(index=3), current=[1]
      → End of elements, incomplete
Exclude 1
  backtrack(index=1), current=[]
  Include 2
    backtrack(index=2), current=[2]
    Include 3
      backtrack(index=3), current=[2,3]
      → RECORD: [2,3]
    Exclude 3
      backtrack(index=3), current=[2]
      → End of elements, incomplete
  Exclude 2
    backtrack(index=2), current=[]
    (Pruned or incomplete: can't get 2 elements from 1 remaining)

Advantages of Include/Exclude

•Mirrors the mathematical recurrence exactly (Pascal's Identity)
•Natural for problems where the decision is inherently binary
•Exactly two branches at each node—clean decision tree
•Easy to modify for 'at most k' or 'at least k' variants

Disadvantages of Include/Exclude

•Deeper recursion: O(n) depth instead of O(k) for the loop-based approach
•More function calls: 2ⁿ theoretical branches (though pruning helps)
•Slightly more complex pruning logic needed
•Order of output may differ from the loop-based method

Combinations, Subsets, and the Power Set

Combinations are intimately related to the subset generation problem. Understanding this relationship illuminates both problems and enables elegant algorithm conversions.

The Power Set:

The power set of a set S, denoted P(S) or 2^S, is the set of all subsets of S, including the empty set and S itself. For a set of n elements, the power set has 2ⁿ elements.

Relationship:

The power set is the union of all k-combinations for k from 0 to n
P(S) = C(S,0) ∪ C(S,1) ∪ ... ∪ C(S,n)
Sum of sizes: C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ

From Subsets to Combinations:

Generating all subsets is simpler than generating k-combinations—just make an include/exclude decision for each element without size constraints. To get k-combinations, filter subsets by size:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Method 1: Generate all subsets, filter by size
function combinationsViaSubsets<T>(elements: T[], k: number): T[][] {
    const allSubsets: T[][] = [];
    const n = elements.length;
    
    // Generate all 2^n subsets using bitmask
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset: T[] = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push(elements[i]);
            }
        }
        if (subset.length === k) {
            allSubsets.push(subset);
        }
    }
    
    return allSubsets;
}
 
// Method 2: Recursive subset generation with size constraint
function combinationsRecursive<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    
    function backtrack(index: number, current: T[]): void {
        // Success: found a subset of exactly size k
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Failure: no more elements to consider
        if (index === elements.length) return;
        
        // Pruning: can't reach size k with remaining elements
        if (elements.length - index < k - current.length) return;
        
        // Include current element
        backtrack(index + 1, [...current, elements[index]]);
        
        // Exclude current element
        backtrack(index + 1, current);
    }
    
    backtrack(0, []);
    return results;
}
 
// Compare outputs
console.log("Via subsets:", combinationsViaSubsets([1,2,3,4], 2));
console.log("Recursive:", combinationsRecursive([1,2,3,4], 2));

Efficiency Consideration

The 'generate all subsets then filter' approach is highly inefficient. It generates 2ⁿ subsets but only keeps C(n,k) of them. For n=30 and k=5, you'd generate 1 billion subsets to keep only 142,506. Always use the direct k-combination algorithm when you need subsets of a specific size.

Bitmask Representation:

An elegant way to represent subsets of n elements is with an n-bit integer (bitmask). Bit i is 1 if element i is included, 0 otherwise.

The bitmask 0b110 (binary) = 6 (decimal) represents {elements[1], elements[2]}
A k-combination corresponds to a bitmask with exactly k bits set
Iterating through all C(n,k) bitmasks with exactly k set bits is non-trivial but possible

Gosper's Hack:

To iterate through all n-bit integers with exactly k bits set:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function* kBitSubsets(n: number, k: number): Generator<number> {
    if (k > n || k < 0) return;
    if (k === 0) {
        yield 0;
        return;
    }
    
    // Start with the lexicographically smallest k-bit number
    let subset = (1 << k) - 1; // k ones: 0b111...1 (k bits)
    const limit = 1 << n;
    
    while (subset < limit) {
        yield subset;
        
        // Gosper's hack to get next subset with same number of bits
        const smallest = subset & -subset;    // Rightmost set bit
        const ripple = subset + smallest;     // Add to cause ripple
        const ones = ((subset ^ ripple) >> 2) / smallest; // Shifted ones
        subset = ripple | ones;
    }
}
 
// Convert bitmask to array
function maskToArray<T>(elements: T[], mask: number): T[] {
    const result: T[] = [];
    for (let i = 0; i < elements.length; i++) {
        if (mask & (1 << i)) {
            result.push(elements[i]);
        }
    }
    return result;
}
 
// Example: C(5, 3)
console.log("3-bit subsets of 5 elements:");
const elements = ['a', 'b', 'c', 'd', 'e'];
for (const mask of kBitSubsets(5, 3)) {
    console.log(`Mask ${mask.toString(2).padStart(5, '0')}: ${maskToArray(elements, mask)}`);
}

Combinations vs. Permutations: A Deep Comparison

Permutations and combinations are two sides of the same combinatorial coin. Understanding their relationship deeply helps in recognizing problem types and choosing appropriate algorithms.

Fundamental Difference:

Permutations: Order matters. [1,2] ≠ [2,1]
Combinations: Order doesn't matter. {1,2} = {2,1}

Mathematical Relationship:

The number of k-permutations (ordered selections of k from n) is:

P(n, k) = n! / (n-k)! = n × (n-1) × ... × (n-k+1)

The number of k-combinations is:

C(n, k) = P(n, k) / k! = n! / (k! × (n-k)!)

Interpretation: P(n, k) counts ordered selections. Dividing by k! 'unorders' them—since each combination corresponds to k! permutations of itself.

Key Differences: Permutations vs Combinations
Aspect	Permutations	Combinations
Order	Matters	Doesn't matter
Count (k from n)	n!/(n-k)!	n!/(k!(n-k)!)
Full (n from n)	n!	1 (only one way to choose all)
Example: 2 from {1,2,3}	[1,2],[1,3],[2,1],[2,3],[3,1],[3,2] = 6	{1,2},{1,3},{2,3} = 3
Algorithm constraint	Track 'used' elements	Maintain ordering (startIndex)
Recursion depth	k (number of positions)	k or n (depends on approach)
Primary template	For each unused, choose/explore/unchoose	For each from startIndex, choose/explore/unchoose
Typical applications	Arrangements, orderings, schedules	Selections, teams, subsets

Converting Between Them:

From Combinations to Permutations: To generate all k-permutations, first generate all k-combinations, then for each combination, generate all k! permutations of those k elements.

From Permutations to Combinations: Generate all k-permutations, then filter/deduplicate by sorting each one (converting to canonical form). This is inefficient—generating C(n,k) × k! permutations to keep only C(n,k).

Algorithm Adaptation:

The permutation algorithm uses a used array; the combination algorithm uses startIndex. These can be unified into a general template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
interface EnumerationConfig<T> {
    elements: T[];
    k: number;                    // How many to select
    ordered: boolean;             // true = permutations, false = combinations
}
 
function enumerate<T>(config: EnumerationConfig<T>): T[][] {
    const { elements, k, ordered } = config;
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(startIndex: number): void {
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Determine iteration range
        const from = ordered ? 0 : startIndex;  // Permutations start from 0
        const to = n;
        
        for (let i = from; i < to; i++) {
            if (ordered && used[i]) continue;  // Permutations: skip used
            // Combinations: ordering prevents revisiting (no check needed)
            
            current.push(elements[i]);
            if (ordered) used[i] = true;
            
            backtrack(i + 1);  // For combinations, advance. For permutations, could pass 0.
            // Actually for permutations we pass any value but check 'used'
            
            current.pop();
            if (ordered) used[i] = false;
        }
    }
    
    backtrack(0);
    return results;
}
 
// Fixed unified template
function enumerateUnified<T>(elements: T[], k: number, ordered: boolean): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    if (ordered) {
        // Permutations: use 'used' array
        const used: boolean[] = new Array(n).fill(false);
        
        function permuteBacktrack(): void {
            if (current.length === k) {
                results.push([...current]);
                return;
            }
            for (let i = 0; i < n; i++) {
                if (used[i]) continue;
                current.push(elements[i]);
                used[i] = true;
                permuteBacktrack();
                current.pop();
                used[i] = false;
            }
        }
        permuteBacktrack();
    } else {
        // Combinations: use startIndex
        function combineBacktrack(start: number): void {
            if (current.length === k) {
                results.push([...current]);
                return;
            }
            for (let i = start; i < n; i++) {
                current.push(elements[i]);
                combineBacktrack(i + 1);
                current.pop();
            }
        }
        combineBacktrack(0);
    }
    
    return results;
}
 
console.log("2-permutations of [1,2,3]:", enumerateUnified([1,2,3], 2, true));
console.log("2-combinations of [1,2,3]:", enumerateUnified([1,2,3], 2, false));

Practical Applications of K-Combinations

K-combination generation appears in countless real-world scenarios. Understanding these applications helps recognize when the combination algorithm applies.

Common Application Domains:

Real-World Applications

•Team Formation: Selecting k members from n candidates for a committee, project team, or jury
•Feature Selection: In machine learning, selecting k features from n available for model training
•Portfolio Construction: Choosing k assets from n options for investment diversification
•Test Case Generation: Selecting k test cases from a larger suite for quick validation
•Menu Combinations: Restaurant 'pick k items' menus, flight/hotel package combinations
•Card Games: Dealing k cards from a deck (bridge hands, poker hands)
•Scheduling: Selecting k time slots from n available for meetings
•Database Queries: Generating queries with k conditions from n possible filters

Example: LeetCode-Style Problem

Many coding interview problems are combination problems in disguise:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Find all combinations of k numbers from candidates that sum to target.
 * Each number may only be used once.
 * 
 * This is a constrained combination problem: generate combinations where
 * sum equals target.
 */
function combinationSum(
    candidates: number[], 
    k: number, 
    target: number
): number[][] {
    const results: number[][] = [];
    const n = candidates.length;
    
    // Sort for potential pruning
    candidates.sort((a, b) => a - b);
    
    function backtrack(startIndex: number, current: number[], currentSum: number): void {
        // Success: k numbers summing to target
        if (current.length === k) {
            if (currentSum === target) {
                results.push([...current]);
            }
            return; // Exactly k elements required
        }
        
        // Pruning: too few elements remain
        if (n - startIndex < k - current.length) return;
        
        for (let i = startIndex; i < n; i++) {
            const newSum = currentSum + candidates[i];
            
            // Pruning: if sorted, larger elements won't help
            if (newSum > target && candidates[i] > 0) {
                // Only break if all remaining are positive
                break;
            }
            
            current.push(candidates[i]);
            backtrack(i + 1, current, newSum);
            current.pop();
        }
    }
    
    backtrack(0, [], 0);
    return results;
}
 
// Example: Find pairs from [1,2,3,4,5] that sum to 6
console.log("Pairs summing to 6:", combinationSum([1,2,3,4,5], 2, 6));
// Output: [[1,5], [2,4]]
 
// Example: Triples from [1,2,3,4,5] summing to 9
console.log("Triples summing to 9:", combinationSum([1,2,3,4,5], 3, 9));
// Output: [[1,3,5], [2,3,4]]

Recognizing Combination Problems

Key indicators that a problem is a combination problem:

• 'Select k items from n' without mentioning order • 'Find all subsets of size k satisfying X' • 'How many ways to choose...' • The phrase 'combination' obviously, but also 'committee', 'team', 'hand' (cards)

If order matters, it's a permutation. If you can repeat elements, it's 'combinations with repetition' (a different algorithm).

Summary and Looking Forward

We've comprehensively explored k-combination generation through backtracking. Let's consolidate the key insights:

Core Concepts:

Combinations are unordered selections; C(n,k) = n!/(k!(n-k)!) distinct k-combinations exist
The key algorithmic insight is ordered selection via startIndex to avoid duplicates
Each combination is generated in canonical (sorted) form exactly once
Pascal's Identity (C(n,k) = C(n-1,k-1) + C(n-1,k)) underlies the include/exclude approach

Implementation Approaches:

Loop with startIndex: Most common, O(k) depth, natural output order
Include/Exclude: Mirrors Pascal's Identity, O(n) depth, good for related problems
Bitmask with Gosper's Hack: Elegant for small n, useful for advanced optimizations

Key Takeaways

•C(n,k) grows slower than n! — Combination enumeration is feasible for larger n than permutation enumeration
•startIndex enforces ordering — The critical invariant that prevents duplicate generation
•Pruning is essential — Early termination when insufficient elements remain dramatically improves efficiency
•Combinations are subsets by size — The power set is the union of all k-combinations
•The template extends — Constrained combinations (sum, product, etc.) add constraints to the base template

What's Next:

In the following pages, we'll explore:

Swapping vs Inserting Approaches: Deep comparison of the two primary paradigms for permutation/combination generation
Handling Duplicates: When elements repeat, how do we avoid generating duplicate combinations and permutations without inefficient post-filtering?

These extensions build on the foundation we've established, completing your toolkit for combinatorial generation problems.

Page Complete

You now possess comprehensive knowledge of k-combination generation. You understand the mathematical foundations, can implement multiple algorithms, recognize combination problems in disguise, and know how to extend the template for constrained variants. This complements your permutation knowledge to form a complete combinatorial generation toolkit.

2 / 4

Loading learning content...

Data Structures & AlgorithmsBacktracking — Systematic Exploration

Permutations & Combinations

LevelIntermediate

Duration90 mins

TopicBacktracking — Systematic Exploration

2 / 4

Generating K-Combinations

The Art of Selection Without Arrangement

What You Will Master

By the end of this page, you will deeply understand:

Mathematical Foundations of Combinations

Understanding the mathematical structure of combinations is essential for understanding why certain algorithmic choices lead to correct and efficient implementations.

Formal Definition:

A k-combination of a set S = {a₁, a₂, ..., aₙ} is a subset of S containing exactly k elements. Since sets are unordered, {1,2,3} and {3,1,2} represent the same combination.

The Binomial Coefficient:

The number of k-combinations from n elements is given by the binomial coefficient:

C(n, k) = n! / (k! × (n-k)!)

This formula has an elegant interpretation:

n! counts all permutations of choosing k elements from n
But since order doesn't matter in combinations, we divide by k! (the number of ways to arrange k chosen elements)
The (n-k)! in the denominator comes from the original factorial formula

Alternative Formula

The binomial coefficient can also be computed as:

C(n, k) = [n × (n-1) × ... × (n-k+1)] / [k × (k-1) × ... × 1]

This form avoids computing large factorials and is numerically more stable for implementation.

Combination Counts: C(n, k) for Various n and k
n \ k	1	2	3	4	5	10	n/2
5	5	10	10	5	1		10
10	10	45	120	210	252	1	252
20	20	190	1,140	4,845	15,504	184,756	184,756
30	30	435	4,060	27,405	142,506	30,045,015	155,117,520
50	50	1,225	19,600	230,300	2,118,760	~10 billion	~126 trillion

Key Observations:

Symmetry: C(n, k) = C(n, n-k). Choosing k elements to include is equivalent to choosing (n-k) elements to exclude.
Maximum at the middle: C(n, k) reaches its maximum when k = n/2 (or nearest integers for odd n). This is where combination counts explode.
Much smaller than factorials: Compare C(20, 10) ≈ 184,756 with 20! ≈ 2.4 × 10¹⁸. Combinations are vastly more tractable than permutations for complete enumeration.
Pascal's Identity: C(n, k) = C(n-1, k-1) + C(n-1, k). This recursive relationship is the foundation of the backtracking approach.

Pascal's Identity Intuition:

Consider element aₙ. In any k-combination, either:

aₙ is included: then we need to choose k-1 elements from the remaining n-1 → C(n-1, k-1) ways
aₙ is excluded: then we need to choose k elements from the remaining n-1 → C(n-1, k) ways

Total: C(n-1, k-1) + C(n-1, k) = C(n, k)

Properties of Combinations

•Unordered Selection: Order of elements doesn't matter; {1,2,3} = {3,2,1}
•No Repetition: Each element appears at most once in a combination
•Subset Relationship: Each k-combination is a k-element subset of the original set
•Cardinality: Exactly C(n,k) distinct k-combinations exist
•Sum of All: C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ (total subsets)

The Backtracking Paradigm for Combinations

The Duplicate Problem:

If we simply try all ways to add k elements to our current combination (as we do for permutations), we'll generate duplicates:

Selecting 2 from [1,2,3]:
- Choose 1, then choose 2 → {1,2}
- Choose 2, then choose 1 → {2,1} = {1,2} (duplicate!)

The Solution: Ordered Selection

We only consider elements that come after the last element we chose. This ensures each combination is generated exactly once, with elements in increasing order:

Selecting 2 from [1,2,3]:
- Start at index 0, choose 1:
  - Consider indices > 0: choose 2 → {1,2}
  - Consider indices > 0: choose 3 → {1,3}
- Start at index 1, choose 2:
  - Consider indices > 1: choose 3 → {2,3}
- Start at index 2, choose 3:
  - No valid second element (need index > 2)

Result: {1,2}, {1,3}, {2,3} — exactly C(3,2) = 3 combinations, no duplicates.

The Canonical Form Principle

The Decision Tree Structure:

For selecting 2 elements from [1, 2, 3, 4], the decision tree looks like:

                        [start]
                    /    |    \    \
                   1     2     3    4      ← First element (start index)
                /|\    /\    |
               2 3 4   3 4   4              ← Second element (index > first)

Each root-to-leaf path of length 2 represents a valid 2-combination. Notice:

After choosing 1, we can choose 2, 3, or 4
After choosing 2, we can only choose 3 or 4 (not 1, as that would duplicate {1,2})
After choosing 3, only 4 remains
After choosing 4, no valid second element exists at higher indices

The Backtracking Invariant:

At any point in the recursion:

current holds a combination prefix with elements in increasing order
startIndex indicates the minimum index from which to select the next element
All elements in current have indices less than startIndex

Backtracking Invariants for Combinations

•Ordering Constraint: Elements in current are always in ascending order (by original index)
•Suffix Selection: We only select from elements[startIndex:] to avoid revisiting earlier elements
•Size Bound: We stop adding elements when current.length === k
•Exhaustiveness: At each position, we try all valid choices (all indices from startIndex to n-1)
•No Repetition: Each element index can appear at most once in current

The Classic Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
function generateCombinations<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    function backtrack(startIndex: number): void {
        // Base case: combination complete
        if (current.length === k) {
            results.push([...current]); // Copy to avoid mutation
            return;
        }
        
        // Pruning: not enough elements left to complete combination
        const remaining = k - current.length;
        const available = n - startIndex;
        if (available < remaining) return; // Early termination
        
        // Try each element from startIndex onwards
        for (let i = startIndex; i < n; i++) {
            // Choose: add element to current combination
            current.push(elements[i]);
            
            // Explore: recurse with next starting position
            backtrack(i + 1); // Note: i + 1, not startIndex + 1
            
            // Unchoose: remove element for next iteration
            current.pop();
        }
    }
    
    backtrack(0);
    return results;
}
 
// Example usage
console.log("C(4, 2) - All 2-combinations of [1,2,3,4]:");
generateCombinations([1, 2, 3, 4], 2).forEach(c => console.log(c));
 
// Output:
// [1, 2]
// [1, 3]
// [1, 4]
// [2, 3]
// [2, 4]
// [3, 4]
 
console.log("\nC(5, 3) - All 3-combinations of ['a','b','c','d','e']:");
generateCombinations(['a', 'b', 'c', 'd', 'e'], 3).forEach(c => console.log(c.join("")));

Execution Trace for C(4, 2):

backtrack(0), current=[]
  i=0: choose 1 → current=[1]
    backtrack(1), current=[1]
      i=1: choose 2 → current=[1,2], length=k → RECORD [1,2]
           unchoose 2 → current=[1]
      i=2: choose 3 → current=[1,3], length=k → RECORD [1,3]
           unchoose 3 → current=[1]
      i=3: choose 4 → current=[1,4], length=k → RECORD [1,4]
           unchoose 4 → current=[1]
    return
  unchoose 1 → current=[]
  i=1: choose 2 → current=[2]
    backtrack(2), current=[2]
      i=2: choose 3 → current=[2,3], length=k → RECORD [2,3]
      i=3: choose 4 → current=[2,4], length=k → RECORD [2,4]
    return
  i=2: choose 3 → current=[3]
    backtrack(3), current=[3]
      i=3: choose 4 → current=[3,4], length=k → RECORD [3,4]
  i=3: choose 4 → current=[4]
    backtrack(4), available=0 < remaining=1 → PRUNE (return)

Notice the pruning on the last iteration: we can't form a 2-combination starting with just element at index 3.

The Critical 'i + 1' Detail

Complexity Analysis:

Time Complexity: O(k × C(n, k))

We generate C(n, k) combinations
Each combination requires O(k) work to copy into results
The recursion tree has O(C(n, k)) leaves plus internal nodes, but the total work is dominated by output generation

Space Complexity: O(k) for the recursion (excluding output)

current array: O(k)
Recursion stack depth: O(k)
Output storage: O(k × C(n, k))

Per-Combination Overhead: O(k) for copying the result array.

The Pruning Optimization:

The early termination check is crucial for efficiency:

const remaining = k - current.length;
const available = n - startIndex;
if (available < remaining) return;

The Include/Exclude Decision Paradigm

This approach mirrors Pascal's Identity: C(n, k) = C(n-1, k-1) + C(n-1, k)

Include element n: reduces to choosing k-1 from remaining n-1
Exclude element n: reduces to choosing k from remaining n-1

Conceptual Model:

We process elements one by one (e.g., left to right). For each element, we branch:

Left branch: Include this element in the combination
Right branch: Exclude this element from the combination

Base cases:

If we've included k elements, we have a complete combination
If we've processed all elements without reaching k, this branch fails
If remaining elements can't possibly complete the combination, prune

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
function combinationsIncludeExclude<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    function backtrack(index: number): void {
        // Base case: combination complete
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Base case: processed all elements without completing
        if (index === n) return;
        
        // Pruning: not enough elements left
        const remaining = k - current.length;
        const available = n - index;
        if (available < remaining) return;
        
        // Branch 1: INCLUDE elements[index]
        current.push(elements[index]);
        backtrack(index + 1);
        current.pop();
        
        // Branch 2: EXCLUDE elements[index]
        backtrack(index + 1);
    }
    
    backtrack(0);
    return results;
}
 
// Trace version for understanding
function combinationsWithTrace<T>(elements: T[], k: number): void {
    const current: T[] = [];
    const indent = (d: number) => "  ".repeat(d);
    
    function backtrack(index: number, depth: number): void {
        console.log(`${indent(depth)}backtrack(index=${index}), current=[${current}]`);
        
        if (current.length === k) {
            console.log(`${indent(depth)}→ RECORD: [${current}]`);
            return;
        }
        if (index === elements.length) {
            console.log(`${indent(depth)}→ End of elements, incomplete`);
            return;
        }
        
        // Include
        console.log(`${indent(depth)}Include ${elements[index]}`);
        current.push(elements[index]);
        backtrack(index + 1, depth + 1);
        current.pop();
        
        // Exclude
        console.log(`${indent(depth)}Exclude ${elements[index]}`);
        backtrack(index + 1, depth + 1);
    }
    
    backtrack(0, 0);
}
 
console.log("Include/Exclude trace for C(3, 2):");
combinationsWithTrace([1, 2, 3], 2);

Trace Output:

backtrack(index=0), current=[]
Include 1
  backtrack(index=1), current=[1]
  Include 2
    backtrack(index=2), current=[1,2]
    → RECORD: [1,2]
  Exclude 2
    backtrack(index=2), current=[1]
    Include 3
      backtrack(index=3), current=[1,3]
      → RECORD: [1,3]
    Exclude 3
      backtrack(index=3), current=[1]
      → End of elements, incomplete
Exclude 1
  backtrack(index=1), current=[]
  Include 2
    backtrack(index=2), current=[2]
    Include 3
      backtrack(index=3), current=[2,3]
      → RECORD: [2,3]
    Exclude 3
      backtrack(index=3), current=[2]
      → End of elements, incomplete
  Exclude 2
    backtrack(index=2), current=[]
    (Pruned or incomplete: can't get 2 elements from 1 remaining)

Advantages of Include/Exclude

•Mirrors the mathematical recurrence exactly (Pascal's Identity)
•Natural for problems where the decision is inherently binary
•Exactly two branches at each node—clean decision tree
•Easy to modify for 'at most k' or 'at least k' variants

Disadvantages of Include/Exclude

•Deeper recursion: O(n) depth instead of O(k) for the loop-based approach
•More function calls: 2ⁿ theoretical branches (though pruning helps)
•Slightly more complex pruning logic needed
•Order of output may differ from the loop-based method

Combinations, Subsets, and the Power Set

Combinations are intimately related to the subset generation problem. Understanding this relationship illuminates both problems and enables elegant algorithm conversions.

The Power Set:

The power set of a set S, denoted P(S) or 2^S, is the set of all subsets of S, including the empty set and S itself. For a set of n elements, the power set has 2ⁿ elements.

Relationship:

The power set is the union of all k-combinations for k from 0 to n
P(S) = C(S,0) ∪ C(S,1) ∪ ... ∪ C(S,n)
Sum of sizes: C(n,0) + C(n,1) + ... + C(n,n) = 2ⁿ

From Subsets to Combinations:

Generating all subsets is simpler than generating k-combinations—just make an include/exclude decision for each element without size constraints. To get k-combinations, filter subsets by size:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Method 1: Generate all subsets, filter by size
function combinationsViaSubsets<T>(elements: T[], k: number): T[][] {
    const allSubsets: T[][] = [];
    const n = elements.length;
    
    // Generate all 2^n subsets using bitmask
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset: T[] = [];
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset.push(elements[i]);
            }
        }
        if (subset.length === k) {
            allSubsets.push(subset);
        }
    }
    
    return allSubsets;
}
 
// Method 2: Recursive subset generation with size constraint
function combinationsRecursive<T>(elements: T[], k: number): T[][] {
    const results: T[][] = [];
    
    function backtrack(index: number, current: T[]): void {
        // Success: found a subset of exactly size k
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Failure: no more elements to consider
        if (index === elements.length) return;
        
        // Pruning: can't reach size k with remaining elements
        if (elements.length - index < k - current.length) return;
        
        // Include current element
        backtrack(index + 1, [...current, elements[index]]);
        
        // Exclude current element
        backtrack(index + 1, current);
    }
    
    backtrack(0, []);
    return results;
}
 
// Compare outputs
console.log("Via subsets:", combinationsViaSubsets([1,2,3,4], 2));
console.log("Recursive:", combinationsRecursive([1,2,3,4], 2));

Efficiency Consideration

Bitmask Representation:

An elegant way to represent subsets of n elements is with an n-bit integer (bitmask). Bit i is 1 if element i is included, 0 otherwise.

The bitmask 0b110 (binary) = 6 (decimal) represents {elements[1], elements[2]}
A k-combination corresponds to a bitmask with exactly k bits set
Iterating through all C(n,k) bitmasks with exactly k set bits is non-trivial but possible

Gosper's Hack:

To iterate through all n-bit integers with exactly k bits set:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function* kBitSubsets(n: number, k: number): Generator<number> {
    if (k > n || k < 0) return;
    if (k === 0) {
        yield 0;
        return;
    }
    
    // Start with the lexicographically smallest k-bit number
    let subset = (1 << k) - 1; // k ones: 0b111...1 (k bits)
    const limit = 1 << n;
    
    while (subset < limit) {
        yield subset;
        
        // Gosper's hack to get next subset with same number of bits
        const smallest = subset & -subset;    // Rightmost set bit
        const ripple = subset + smallest;     // Add to cause ripple
        const ones = ((subset ^ ripple) >> 2) / smallest; // Shifted ones
        subset = ripple | ones;
    }
}
 
// Convert bitmask to array
function maskToArray<T>(elements: T[], mask: number): T[] {
    const result: T[] = [];
    for (let i = 0; i < elements.length; i++) {
        if (mask & (1 << i)) {
            result.push(elements[i]);
        }
    }
    return result;
}
 
// Example: C(5, 3)
console.log("3-bit subsets of 5 elements:");
const elements = ['a', 'b', 'c', 'd', 'e'];
for (const mask of kBitSubsets(5, 3)) {
    console.log(`Mask ${mask.toString(2).padStart(5, '0')}: ${maskToArray(elements, mask)}`);
}

Combinations vs. Permutations: A Deep Comparison

Permutations and combinations are two sides of the same combinatorial coin. Understanding their relationship deeply helps in recognizing problem types and choosing appropriate algorithms.

Fundamental Difference:

Permutations: Order matters. [1,2] ≠ [2,1]
Combinations: Order doesn't matter. {1,2} = {2,1}

Mathematical Relationship:

The number of k-permutations (ordered selections of k from n) is:

P(n, k) = n! / (n-k)! = n × (n-1) × ... × (n-k+1)

The number of k-combinations is:

C(n, k) = P(n, k) / k! = n! / (k! × (n-k)!)

Interpretation: P(n, k) counts ordered selections. Dividing by k! 'unorders' them—since each combination corresponds to k! permutations of itself.

Key Differences: Permutations vs Combinations
Aspect	Permutations	Combinations
Order	Matters	Doesn't matter
Count (k from n)	n!/(n-k)!	n!/(k!(n-k)!)
Full (n from n)	n!	1 (only one way to choose all)
Example: 2 from {1,2,3}	[1,2],[1,3],[2,1],[2,3],[3,1],[3,2] = 6	{1,2},{1,3},{2,3} = 3
Algorithm constraint	Track 'used' elements	Maintain ordering (startIndex)
Recursion depth	k (number of positions)	k or n (depends on approach)
Primary template	For each unused, choose/explore/unchoose	For each from startIndex, choose/explore/unchoose
Typical applications	Arrangements, orderings, schedules	Selections, teams, subsets

Converting Between Them:

From Combinations to Permutations: To generate all k-permutations, first generate all k-combinations, then for each combination, generate all k! permutations of those k elements.

Algorithm Adaptation:

The permutation algorithm uses a used array; the combination algorithm uses startIndex. These can be unified into a general template:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
interface EnumerationConfig<T> {
    elements: T[];
    k: number;                    // How many to select
    ordered: boolean;             // true = permutations, false = combinations
}
 
function enumerate<T>(config: EnumerationConfig<T>): T[][] {
    const { elements, k, ordered } = config;
    const results: T[][] = [];
    const n = elements.length;
    const used: boolean[] = new Array(n).fill(false);
    const current: T[] = [];
    
    function backtrack(startIndex: number): void {
        if (current.length === k) {
            results.push([...current]);
            return;
        }
        
        // Determine iteration range
        const from = ordered ? 0 : startIndex;  // Permutations start from 0
        const to = n;
        
        for (let i = from; i < to; i++) {
            if (ordered && used[i]) continue;  // Permutations: skip used
            // Combinations: ordering prevents revisiting (no check needed)
            
            current.push(elements[i]);
            if (ordered) used[i] = true;
            
            backtrack(i + 1);  // For combinations, advance. For permutations, could pass 0.
            // Actually for permutations we pass any value but check 'used'
            
            current.pop();
            if (ordered) used[i] = false;
        }
    }
    
    backtrack(0);
    return results;
}
 
// Fixed unified template
function enumerateUnified<T>(elements: T[], k: number, ordered: boolean): T[][] {
    const results: T[][] = [];
    const n = elements.length;
    const current: T[] = [];
    
    if (ordered) {
        // Permutations: use 'used' array
        const used: boolean[] = new Array(n).fill(false);
        
        function permuteBacktrack(): void {
            if (current.length === k) {
                results.push([...current]);
                return;
            }
            for (let i = 0; i < n; i++) {
                if (used[i]) continue;
                current.push(elements[i]);
                used[i] = true;
                permuteBacktrack();
                current.pop();
                used[i] = false;
            }
        }
        permuteBacktrack();
    } else {
        // Combinations: use startIndex
        function combineBacktrack(start: number): void {
            if (current.length === k) {
                results.push([...current]);
                return;
            }
            for (let i = start; i < n; i++) {
                current.push(elements[i]);
                combineBacktrack(i + 1);
                current.pop();
            }
        }
        combineBacktrack(0);
    }
    
    return results;
}
 
console.log("2-permutations of [1,2,3]:", enumerateUnified([1,2,3], 2, true));
console.log("2-combinations of [1,2,3]:", enumerateUnified([1,2,3], 2, false));

Practical Applications of K-Combinations

K-combination generation appears in countless real-world scenarios. Understanding these applications helps recognize when the combination algorithm applies.

Common Application Domains:

Real-World Applications

•Team Formation: Selecting k members from n candidates for a committee, project team, or jury
•Feature Selection: In machine learning, selecting k features from n available for model training
•Portfolio Construction: Choosing k assets from n options for investment diversification
•Test Case Generation: Selecting k test cases from a larger suite for quick validation
•Menu Combinations: Restaurant 'pick k items' menus, flight/hotel package combinations
•Card Games: Dealing k cards from a deck (bridge hands, poker hands)
•Scheduling: Selecting k time slots from n available for meetings
•Database Queries: Generating queries with k conditions from n possible filters

Example: LeetCode-Style Problem

Many coding interview problems are combination problems in disguise:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Find all combinations of k numbers from candidates that sum to target.
 * Each number may only be used once.
 * 
 * This is a constrained combination problem: generate combinations where
 * sum equals target.
 */
function combinationSum(
    candidates: number[], 
    k: number, 
    target: number
): number[][] {
    const results: number[][] = [];
    const n = candidates.length;
    
    // Sort for potential pruning
    candidates.sort((a, b) => a - b);
    
    function backtrack(startIndex: number, current: number[], currentSum: number): void {
        // Success: k numbers summing to target
        if (current.length === k) {
            if (currentSum === target) {
                results.push([...current]);
            }
            return; // Exactly k elements required
        }
        
        // Pruning: too few elements remain
        if (n - startIndex < k - current.length) return;
        
        for (let i = startIndex; i < n; i++) {
            const newSum = currentSum + candidates[i];
            
            // Pruning: if sorted, larger elements won't help
            if (newSum > target && candidates[i] > 0) {
                // Only break if all remaining are positive
                break;
            }
            
            current.push(candidates[i]);
            backtrack(i + 1, current, newSum);
            current.pop();
        }
    }
    
    backtrack(0, [], 0);
    return results;
}
 
// Example: Find pairs from [1,2,3,4,5] that sum to 6
console.log("Pairs summing to 6:", combinationSum([1,2,3,4,5], 2, 6));
// Output: [[1,5], [2,4]]
 
// Example: Triples from [1,2,3,4,5] summing to 9
console.log("Triples summing to 9:", combinationSum([1,2,3,4,5], 3, 9));
// Output: [[1,3,5], [2,3,4]]

Recognizing Combination Problems

Key indicators that a problem is a combination problem:

If order matters, it's a permutation. If you can repeat elements, it's 'combinations with repetition' (a different algorithm).

Summary and Looking Forward

We've comprehensively explored k-combination generation through backtracking. Let's consolidate the key insights:

Core Concepts:

Combinations are unordered selections; C(n,k) = n!/(k!(n-k)!) distinct k-combinations exist
The key algorithmic insight is ordered selection via startIndex to avoid duplicates
Each combination is generated in canonical (sorted) form exactly once
Pascal's Identity (C(n,k) = C(n-1,k-1) + C(n-1,k)) underlies the include/exclude approach

Implementation Approaches:

Loop with startIndex: Most common, O(k) depth, natural output order
Include/Exclude: Mirrors Pascal's Identity, O(n) depth, good for related problems
Bitmask with Gosper's Hack: Elegant for small n, useful for advanced optimizations

Key Takeaways

•C(n,k) grows slower than n! — Combination enumeration is feasible for larger n than permutation enumeration
•startIndex enforces ordering — The critical invariant that prevents duplicate generation
•Pruning is essential — Early termination when insufficient elements remain dramatically improves efficiency
•Combinations are subsets by size — The power set is the union of all k-combinations
•The template extends — Constrained combinations (sum, product, etc.) add constraints to the base template

What's Next:

In the following pages, we'll explore:

Swapping vs Inserting Approaches: Deep comparison of the two primary paradigms for permutation/combination generation
Handling Duplicates: When elements repeat, how do we avoid generating duplicate combinations and permutations without inefficient post-filtering?

These extensions build on the foundation we've established, completing your toolkit for combinatorial generation problems.

Page Complete

2 / 4