Algorithms from zero
Combinations
In the previous lesson, you learned to generate permutations by choosing which unused item goes next, and subsets by choosing to include or exclude each element. Now comes a third variation: choose k items from n items, but this time order does not matter. {A, B} and {B, A} are the same combination, even though they are different permutations. The trick to avoid generating the same combination twice is to walk the items in a fixed order and enforce that your choices only move forward—never backward. This single idea, the start index, transforms a subtle problem into a clean one.
After this lesson you can write a backtracking function to generate all combinations of k items from n items. You understand why there are C(n, k) = n! / (k!(n-k)!) combinations—the binomial coefficient. You recognize the start index trick: by only considering items from a given index onward, you naturally avoid duplicates and prune branches early. You contrast combinations with permutations and subsets to see how the same template adapts to different choice logic.
Combinations: choose k from n
A combination is a selection of k items from a set of n items, where order does not matter. The set {A, B, C} has three 2-combinations: {A, B}, {A, C}, {B, C}. Note that {A, B} and {B, A} are the same combination—we do not count them twice.
Example: how many ways can you choose 2 people from a group of 4?
{1, 2},{1, 3},{1, 4},{2, 3},{2, 4},{3, 4}
Total: 6 combinations. In general, the count is C(n, k) = n! / (k!(n-k)!), also written as “n choose k” or the binomial coefficient.
Why C(n, k) and not n!?
Permutations count all orderings: {A, B} and {B, A} are different. Combinations count only selections: {A, B} and {B, A} are the same. To convert permutations to combinations, divide out the k! orderings within the chosen set. So C(n, k) = P(n, k) / k! = n! / ((n-k)! × k!).
Combinations vs. permutations: the start index trick
With permutations, you ask: “which unused item goes next?” You track a used array to avoid re-picking the same item.
With combinations, you ask: “do I include this item or skip it?” But unlike subsets—where you branch on every item—here you can be smarter. You enforce an order: if you include item at index i, the next item you consider must come at index i+1 or later. This prevents generating the same set twice with different orderings.
The backtracking shape for combinations
function combinations(arr, k, start, current, result):
if len(current) == k:
result.append(copy(current))
return
for i in range(start, len(arr)):
# Choice: include arr[i]
current.push(arr[i])
combinations(arr, k, i + 1, current, result) # Next start is i+1
current.pop()Key insight: the loop begins at start, not at 0. So if you choose arr[2], the next recursive call only considers arr[3], arr[4], etc. Earlier items (arr[0], arr[1]) are never revisited. This guarantees no duplicates.
Example: combinations of {1, 2, 3, 4}, choose 2
- Start at i=0: include 1, then look at indices 1+ →
{1,2},{1,3},{1,4}. - Start at i=1: include 2, then look at indices 2+ →
{2,3},{2,4}. - Start at i=2: include 3, then look at indices 3+ →
{3,4}. - Start at i=3: include 4, but no indices left after 3. (This pruning happens naturally.)
Result: 6 combinations. No duplicate like {2, 1} because we never explore it—once we pick 1, we only consider 2+.
Pruning: early stopping
At any point, if the number of items left plus the current size cannot reach k, prune the branch.
remaining = len(arr) - start
if len(current) + remaining < k:
return # Not enough items left to reach kFor example, if you have chosen 1 item, need k=3, and only 2 items remain, stop—you cannot reach k=3. This cuts many branches.
Combinations vs. subsets vs. permutations: the template recap
| Problem | Choice | Loop Start | Base Case | Output Count |
|---|---|---|---|---|
| Subsets | include/exclude each | N/A (depth-based) | depth == n | 2^n |
| Permutations | which unused item next | 0 (always) | size == n | n! |
| Combinations | include/skip in order | start index | size == k | C(n,k) |
All three use the same choose-explore-undo pattern. The difference is in the loop logic and the base case.
From the math track CombinationsLet us code combinations.
Example: Generate all combinations of k items from n items
function combinations(arr, k) {
const result = [];
function backtrack(start, current) {
// Base case: built a complete combination
if (current.length === k) {
result.push([...current]);
return;
}
// Pruning: not enough items left
const remaining = arr.length - start;
if (current.length + remaining < k) {
return;
}
// Try each item from 'start' onward
for (let i = start; i < arr.length; i++) {
// Choice: include arr[i]
current.push(arr[i]);
backtrack(i + 1, current); // Next start is i+1
current.pop(); // Undo
}
}
backtrack(0, []);
return result;
}
console.log(combinations([1, 2, 3, 4], 2));
// Output: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]Try it:
Example: Contrast with permutations
Permutations of {1, 2, 3} choose 2 (order matters):
(1, 2),(1, 3),(2, 1),(2, 3),(3, 1),(3, 2)— 6 permutations.
Combinations of {1, 2, 3} choose 2 (order does not matter):
{1, 2},{1, 3},{2, 3}— 3 combinations.
The difference: {1, 2} and {2, 1} are counted once as a combination (because they are the same set), but twice as permutations (because the order differs).
Let us trace the generation of all combinations of {1, 2, 3, 4}, choosing 2.
1
function backtrack(start, current) {
2
if (current.length === k) {
3
result.push([...current]); return;
4
}
5
for (let i = start; i < arr.length; i++) {
6
current.push(arr[i]);
7
backtrack(i + 1, current);
8
current.pop();
9
}
The key: the start index ensures we move forward only. When we pick 1, we only look at 2, 3, 4 (never 0 again). When we pick 2, we only look at 3, 4 (never 1 again). This natural ordering prevents duplicates like 1.
Time: O(C(n, k) × k), Space: O(k)
- The recursion tree has depth k (choose k items).
- At each level, the branching factor decreases: n choices at level 0, then n-1, n-2, etc.
- The total number of leaves = C(n, k) (the number of distinct combinations).
- Each leaf records one combination, which takes O(k) time (copying k elements).
- Time = C(n, k) × O(k) = O(C(n, k) × k).
- Space (call stack) = O(k) (depth of recursion).
How big is C(n, k)?
C(n, k) = n! / (k!(n-k)!) grows with n but depends heavily on k.
- C(n, 1) = n (choose 1 from n).
- C(n, 2) = n(n-1) / 2 (choose 2 from n).
- C(n, n) = 1 (choose all).
- Maximum at k = n/2. For n=20, k=10, that is C(20, 10) ≈ 184,756.
For small k relative to n, C(n, k) is much smaller than n!. For example, C(100, 2) = 4,950, but 100! is astronomically large. This makes combinations practical when k is fixed and small.
Pruning saves time
The pruning check if (current.length + remaining < k) return; cuts branches early. In the worst case (k = n/2), pruning provides minimal gain, but for fixed small k, it eliminates many branches quickly.
How many combinations are there of choosing 2 items from a set of 5?
How many combinations of choosing 3 items from {1, 2, 3, 4, 5}?
What is the key difference between generating permutations and generating combinations?
Why does the start index prevent duplicate combinations?
What is C(6, 3)?
Common mistake
Mistake 1: Not copying the combination. You build a combination in current, and when you reach size k, you must copy it before appending to result. If you append the reference, all combinations in result point to the same array. When you pop from current, all of them lose that element.
// WRONG
if (current.length === k) {
result.push(current); // BUG: same reference
return;
}
// CORRECT
if (current.length === k) {
result.push([...current]); // Copy the array
return;
}Mistake 2: Forgetting the start index. If you always start the loop from 0, you generate the same combination multiple times in different orders.
// WRONG: starts from 0 every time, generates duplicates
for (let i = 0; i < arr.length; i++) {
current.push(arr[i]);
backtrack(0, current); // BUG: next start is 0, not i+1
current.pop();
}
// CORRECT: next start is i+1
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
backtrack(i + 1, current); // Next start is i+1
current.pop();
}Mistake 3: Missing pruning. Without the pruning check, you explore branches that cannot possibly reach k items. This is inefficient, though still correct.
// Works but slow
for (let i = start; i < arr.length; i++) {
current.push(arr[i]);
backtrack(i + 1, current);
current.pop();
}
// Better: prune early
const remaining = arr.length - start;
if (current.length + remaining < k) {
return;
}The start index and the copy are not optional—without them, your algorithm fails or produces duplicates.
You generate all combinations of 4 items from an array of 6. How many combinations are there, and what is the time complexity?
Combinations: Generate every way to choose k items from n items, where order does not matter. {A, B} and {B, A} are the same combination.
The count: C(n, k) = n! / (k!(n-k)!) — the binomial coefficient, also called “n choose k”.
The start index trick: To avoid generating the same combination in different orders, enforce a forward-only walk. Once you pick arr[i], only consider arr[i+1] and later. Never go backward. This prevents duplicates and enables pruning.
Template: At each step, choose to include the current item (and move start forward to i+1) or skip it (still move start to i+1). Recurse until you have chosen k items.
Complexity: O(C(n, k) × k) time and O(k) space. C(n, k) is much smaller than n! when k is small and fixed, making combinations practical for problems like “find all pairs” or “find all triples”.
Contrasts: Subsets branch on every element (2^n outputs), permutations track which items are used (n! outputs), combinations use a start index to enforce order (C(n, k) outputs). All three use the choose-explore-undo pattern with different choice logic.