sko.kr

Algorithms - 19. Combinations (Backtracking)

algorithmsbacktrackingcombinationsrecursioncombinatorics
By sko•10/9/2025•8 min read

When to use Combinations Algorithm

Use the combinations algorithm when you need to generate all possible selections of k items from n choices where order doesn't matter. While most commonly used for mathematical combinations (n choose k), it can be adapted for:

  • Team selection from a pool of candidates (classic use case)
  • Feature subset selection for machine learning models
  • Resource allocation problems with limited slots
  • Menu combinations (choosing k dishes from n options)
  • Investment portfolios (selecting k stocks from n available)
  • Committee formation from organization members
  • Any problem requiring all possible k-sized subsets from a larger set

The key criteria: You need exactly k items, order doesn't matter (ABC = BAC = CBA), and you want all valid selections.

Example problem

Team Building: From 5 employees [1, 2, 3, 4, 5], form all possible 3-person teams for a project.

After generating all combinations:

  • Team 1: [1, 2, 3]
  • Team 2: [1, 2, 4]
  • Team 3: [1, 2, 5]
  • Team 4: [1, 3, 4]
  • Team 5: [1, 3, 5]
  • Team 6: [1, 4, 5]
  • Team 7: [2, 3, 4]
  • Team 8: [2, 3, 5]
  • Team 9: [2, 4, 5]
  • Team 10: [3, 4, 5]

Total: 10 unique teams (which matches C(5,3) = 10)

What the Combinations Algorithm Actually Does

The combinations algorithm systematically explores a decision tree where at each level, you decide whether to include or exclude an element in your current combination.

Think of it like packing a suitcase with exactly k items:

  • You go through items one by one
  • For each item, you decide: "Take it" or "Skip it"
  • Once you have k items, you've found one valid combination
  • You backtrack to try different choices

How the Algorithm Works

The Include/Exclude Decision Process

Starting from element 1, the algorithm:

  1. Makes a choice about the current element (include or exclude)
  2. Explores that path recursively with remaining elements
  3. Backtracks when reaching k elements or running out of options
  4. Tries the alternative choice for systematic exploration

The Two Main Approaches

Approach 1: Binary Decision Tree (Include/Exclude)

  • At each element: explicitly try both "include" and "exclude"
  • Explores all 2^n possibilities but only saves valid k-sized combinations
  • More intuitive but less efficient

Approach 2: Forward Selection

  • At each position: try all remaining elements as the next choice
  • Only explores paths that lead to valid combinations
  • More efficient by pruning impossible branches early

When These Decisions Happen

The algorithm makes decisions at every recursive call:

// Decision point: include current element
combination.push(currentElement);
explore(nextElement); // Continue with this choice
combination.pop(); // Backtrack

// Decision point: exclude current element
explore(nextElement); // Continue without including

The beauty is that backtracking automatically undoes choices, allowing systematic exploration of all possibilities without missing any or creating duplicates.

Single most important insight

Combinations are paths through a decision tree where each level represents choosing or skipping an element - and by tracking our current selection size and backtracking when we reach k elements, we systematically generate all valid k-sized subsets without duplicates.

Mental note: The algorithm's genius lies in treating combination generation as a series of include/exclude decisions. At each element, we only need to decide: "Should I include this element in my current combination?" After including it, we explore what combinations we can make with remaining elements. When we backtrack, we undo that decision and try the alternative. This simple decision pattern automatically generates all C(n,k) combinations.

Decision Framework

The algorithm makes decisions at two key points:

Core Decision: Include or Exclude

  • Include current element → recurse with it in the combination
  • Exclude current element → recurse without it

Termination Decisions:

  • Have k elements? → Save this valid combination
  • Passed all n elements? → No more elements to consider
  • Not enough elements left to reach k? → Prune this branch (optimization)

Optimization: Early Termination

A key optimization is recognizing when we can't possibly reach k elements:

// If we need 3 more elements but only 2 remain, stop exploring
const elementsNeeded = k - currentCombination.length;
const elementsRemaining = n - currentIndex + 1;
if (elementsNeeded > elementsRemaining) return; // Prune branch

This pruning dramatically reduces the search space from O(2^n) to O(C(n,k)).

Code

// Approach 1: Binary Decision Tree (Include/Exclude Pattern)
function generateCombinations(totalNumbers, targetSize) {
  const allCombinations = [];

  function exploreDecisions(currentNumber, selectedNumbers) {
    // Check if we've selected enough numbers
    const haveEnoughNumbers = selectedNumbers.length === targetSize;
    if (haveEnoughNumbers) {
      // Found a valid combination - save a copy
      const validCombination = [...selectedNumbers];
      allCombinations.push(validCombination);
      return;
    }

    // Check if we've gone through all numbers
    const noMoreNumbersToConsider = currentNumber > totalNumbers;
    if (noMoreNumbersToConsider) {
      return;
    }

    // DECISION FRAMEWORK: Include current number
    // Choice 1: Include this number in our combination
    selectedNumbers.push(currentNumber);
    const nextNumber = currentNumber + 1;
    exploreDecisions(nextNumber, selectedNumbers);

    // Backtrack: undo the inclusion
    selectedNumbers.pop();

    // DECISION FRAMEWORK: Exclude current number
    // Choice 2: Skip this number and try the next one
    exploreDecisions(nextNumber, selectedNumbers);
  }

  const startingNumber = 1;
  const emptySelection = [];
  exploreDecisions(startingNumber, emptySelection);

  return allCombinations;
}

// Approach 2: Forward Selection (More Efficient)
function generateCombinationsOptimized(totalNumbers, targetSize) {
  const allCombinations = [];

  function selectNextNumber(startFrom, selectedNumbers) {
    // Check if we've selected enough numbers
    const haveEnoughNumbers = selectedNumbers.length === targetSize;
    if (haveEnoughNumbers) {
      // Found a valid combination - save a copy
      const validCombination = [...selectedNumbers];
      allCombinations.push(validCombination);
      return;
    }

    // Early termination optimization
    const numbersStillNeeded = targetSize - selectedNumbers.length;
    const numbersRemaining = totalNumbers - startFrom + 1;
    const impossibleToReachTarget = numbersStillNeeded > numbersRemaining;

    if (impossibleToReachTarget) {
      return; // Can't possibly select enough numbers
    }

    // DECISION FRAMEWORK: Try each remaining number
    for (
      let currentNumber = startFrom;
      currentNumber <= totalNumbers;
      currentNumber++
    ) {
      // Select this number
      selectedNumbers.push(currentNumber);

      // Continue selecting from the remaining numbers
      const nextStartingPoint = currentNumber + 1;
      selectNextNumber(nextStartingPoint, selectedNumbers);

      // Backtrack: deselect this number to try others
      selectedNumbers.pop();
    }
  }

  const startingNumber = 1;
  const emptySelection = [];
  selectNextNumber(startingNumber, emptySelection);

  return allCombinations;
}

// === EXAMPLE USAGE: Team Building Problem ===
// Problem: Select 3-person teams from 5 employees [1, 2, 3, 4, 5]

const numberOfEmployees = 5;
const teamSize = 3;

console.log("Team Building: Choose 3 from 5 employees");
console.log("Employees: [1, 2, 3, 4, 5]");
console.log("Team size: 3");

// Method 1: Using binary decision tree
const teamsMethod1 = generateCombinations(numberOfEmployees, teamSize);

console.log("\n=== Binary Decision Tree Results ===");
console.log(`Found ${teamsMethod1.length} possible teams:`);
teamsMethod1.forEach((team, index) => {
  const teamNumber = index + 1;
  const teamMembers = team.join(", ");
  console.log(`Team ${teamNumber}: [${teamMembers}]`);
});

// Method 2: Using forward selection
const teamsMethod2 = generateCombinationsOptimized(numberOfEmployees, teamSize);

console.log("\n=== Forward Selection Results ===");
console.log(`Found ${teamsMethod2.length} possible teams:`);
teamsMethod2.forEach((team, index) => {
  const teamNumber = index + 1;
  const teamMembers = team.join(", ");
  console.log(`Team ${teamNumber}: [${teamMembers}]`);
});

// Verify against mathematical formula
function calculateFactorial(n) {
  if (n <= 1) return 1;
  return n * calculateFactorial(n - 1);
}

const nFactorial = calculateFactorial(5);
const kFactorial = calculateFactorial(3);
const nMinusKFactorial = calculateFactorial(2);
const expectedCombinations = nFactorial / (kFactorial * nMinusKFactorial);

console.log("\n=== Mathematical Verification ===");
console.log(`Formula: C(5,3) = 5! / (3! × 2!)`);
console.log(`Expected: ${expectedCombinations} combinations`);
console.log(`Method 1 generated: ${teamsMethod1.length} combinations`);
console.log(`Method 2 generated: ${teamsMethod2.length} combinations`);
console.log(
  `Verification: ${
    teamsMethod1.length === expectedCombinations ? "✓ Correct" : "✗ Error"
  }`
);

Doubt buster

Common doubt: "Why do we need to make a copy ([...currentCombination]) when saving the result? Can't we just push the array directly? Also, why does the include/exclude approach work - won't we miss combinations or create duplicates?"

Why copying is absolutely necessary

Let's trace what happens WITHOUT copying:

// BROKEN VERSION - without copying
function brokenCombinations(n, k) {
  const allCombinations = [];

  function backtrack(startNumber, currentCombination) {
    if (currentCombination.length === k) {
      allCombinations.push(currentCombination); // NO COPY - BUG!
      return;
    }
    // ... rest of logic
  }
}

// What actually happens:
// 1. currentCombination = [1, 2, 3] → push this array reference
// 2. Backtrack: currentCombination becomes [1, 2, 4]
// 3. The SAME array in allCombinations now shows [1, 2, 4]!
// 4. Final result: all entries point to the SAME array

Without copying, you're storing references to the same array object that keeps changing. At the end, all your "combinations" would show the same final state of the array!

Why include/exclude doesn't miss combinations or create duplicates

The key insight is that we're making decisions in a fixed order (elements 1, 2, 3, 4, 5...):

Systematic exploration prevents duplicates:

Decision tree for n=3, k=2:
                 Start
                /      \
            Include 1   Exclude 1
           /         \       \
      Include 2   Exclude 2  Include 2
        /           \           \
    Include 3    Include 3   Include 3
    [1,2,3]❌     [1,3]✓      [2,3]✓
    (too many)   (valid!)    (valid!)

Each path represents a UNIQUE series of decisions:

  • [1,2] = Include 1, Include 2
  • [1,3] = Include 1, Exclude 2, Include 3
  • [2,3] = Exclude 1, Include 2, Include 3

Since we always consider elements in order (1→2→3), we can never get duplicates like [2,1] or [3,2].

Why we can't miss any combinations

The algorithm explores ALL possible decision sequences:

For n=4, k=2, we need to find all 2-element subsets:

Element decisions:     Resulting combination:
1=✓, 2=✓, stop     →  [1,2]
1=✓, 2=✗, 3=✓, stop →  [1,3]
1=✓, 2=✗, 3=✗, 4=✓  →  [1,4]
1=✗, 2=✓, 3=✓, stop →  [2,3]
1=✗, 2=✓, 3=✗, 4=✓  →  [2,4]
1=✗, 2=✗, 3=✓, 4=✓  →  [3,4]

Every valid combination corresponds to exactly one sequence of include/exclude decisions. The binary tree has 2^n leaf nodes (all possible decision sequences), and we filter for those with exactly k includes.

Concrete example: Can't miss [2,4]

Let's verify we find [2,4] from [1,2,3,4] with k=2:

backtrack(1, []);
// Exclude 1
backtrack(2, []);
// Include 2
backtrack(3, [2]);
// Exclude 3
backtrack(4, [2]);
// Include 4
backtrack(5, [2, 4]);
// length = 2 = k, save [2,4] ✓

The path "Exclude 1 → Include 2 → Exclude 3 → Include 4" uniquely generates [2,4].

Mathematical proof of completeness

Every k-subset maps to exactly one path:

  1. A k-subset is defined by which k elements are chosen
  2. For each element i, we either include it (if i is in the subset) or exclude it
  3. This creates a unique path through the decision tree
  4. Therefore: # of k-subsets = # of valid paths = C(n,k)

Example verification:

  • n=5, k=3 → We should get C(5,3) = 10 combinations
  • Our algorithm generates: [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]
  • Count: 10 ✓

The algorithm is complete (finds all combinations) and sound (no duplicates) because it systematically explores all decision paths in a fixed order!

← Back to Blog