Generate All Combinations
Generate all C(n,k) combinations - all possible selections of k elements from n elements where order doesn't matter. Unlike permutations, {1,2,3} and {3,2,1} are the same combination. Uses backtracking to explore choices systematically, ensuring each combination is counted once. Fundamental in statistics, probability, lottery systems, and feature selection in machine learning.
Visualization
Interactive visualization for Generate All Combinations
Interactive visualization with step-by-step execution
Implementation
1function combine(n: number, k: number): number[][] {
2 const result: number[][] = [];
3 const current: number[] = [];
4
5 function backtrack(start: number): void {
6 if (current.length === k) {
7 result.push([...current]);
8 return;
9 }
10
11 for (let i = start; i <= n; i++) {
12 current.push(i);
13 backtrack(i + 1);
14 current.pop();
15 }
16 }
17
18 backtrack(1);
19 return result;
20}Deep Dive
Theoretical Foundation
Combination generation uses backtracking with a 'start' parameter to avoid duplicates. For each position, we try elements from 'start' onwards (not all elements like permutations). This ensures we only generate combinations in ascending order, avoiding duplicates. Total combinations: C(n,k) = n!/(k!(n-k)!). Time: O(C(n,k)) to generate all combinations, O(k) to copy each, total O(C(n,k) × k). Space: O(k) recursion depth.
Complexity
Time
O(C(n,k) × k)
O(C(n,k) × k)
O(C(n,k) × k)
Space
O(C(n,k) × k) output + O(k) recursion
Applications
Industry Use
Lottery number generation
Team selection from pool of candidates
Feature selection in ML (choose k from n features)
Subset sum problem
Card game combinations
Statistical sampling
Chemistry molecular combinations
Use Cases
Related Algorithms
Tower of Hanoi
Tower of Hanoi is a classic mathematical puzzle invented by French mathematician Édouard Lucas in 1883. The puzzle consists of three rods and n disks of different sizes that can slide onto any rod. The objective is to move the entire stack from one rod to another, following rules: (1) only one disk can be moved at a time, (2) only the top disk from any rod can be moved, (3) a larger disk cannot be placed on a smaller disk. The elegant recursive solution requires exactly 2^n - 1 moves.
Generate All Permutations
Generate all possible arrangements (permutations) of n distinct elements. For n elements, there are exactly n! permutations. This classic backtracking problem demonstrates recursive exploration of the solution space, where we systematically build permutations by choosing elements and backtracking when complete. Used in combinatorics, constraint satisfaction, and optimization problems.
Generate All Subsets (Power Set)
Generate the power set - all 2^n possible subsets of an n-element set, including the empty set and the set itself. For example, subsets of {1,2,3} are: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}. Can be elegantly solved using recursion, iteration, or bit manipulation. Essential in combinatorial optimization and constraint satisfaction.
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.