Combinations & subset search

Overview

Combinations count unordered selections, and they come in two flavours of code. Counting uses Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) — each element is either chosen or not — though computing it multiplicatively is far more practical. Enumerating uses the same include/exclude idea as an actual recursion over the elements, which is the shape you need when the question is not "how many" but "is there a selection satisfying this property". The subset-sum search in this lesson is exactly that: try including the current element, then try excluding it, and prune whenever the remaining elements cannot possibly reach the target.

Why it matters

Include/exclude recursion is the general tool for searching a selection space, and the pruning that goes with it is what keeps such a search from exploding. Combination counts also give you the size of that space up front — C(50,25) is about 1.26 x 10^14, which tells you immediately that enumeration is off the table and a DP formulation is required.

Core concepts

Pascal's identity. C(n,k) = C(n-1,k-1) + C(n-1,k): consider one specific element — either it is in the selection (choose k-1 from the rest) or it is not (choose k from the rest). Base cases: C(n,0) = C(n,n) = 1, and C(n,k) = 0 when k < 0 or k > n.

Symmetry. C(n,k) == C(n,n-k), so replacing k with min(k, n-k) halves the work and greatly reduces overflow risk.

Multiplicative computation. C(n,k) = prod over i of (n-i)/(i+1), evaluated as r = r * (n-i) / (i+1). Each intermediate is exactly divisible, so integer arithmetic stays exact — but the multiplication happens before the division, so the intermediate can overflow even when the answer would not.

Include/exclude search. f(i, k, t) asks whether k elements from a[i..] sum to t. Recurse as include f(i+1, k-1, t-a[i]) OR exclude f(i+1, k, t).

Pruning is essential. Stop early when k == 0 (check t == 0), when i >= n, when fewer than k elements remain (k > n-i), or when t < 0 for non-negative inputs. Each of these cuts a subtree; without them the search is 2^n.

Syntax notes

/* multiplicative binomial - exact in integers, uses the symmetry */
long long choose(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;                    /* C(n,k) == C(n,n-k) */
    long long r = 1;
    for (int i = 0; i < k; i++)
        r = r * (n - i) / (i + 1);               /* divides exactly at each step */
    return r;
}

/* include/exclude search with pruning: can k elements of a[i..] sum to t? */
int ksum(const int *a, int n, int i, int k, int t) {
    if (k == 0) return t == 0;                   /* selected enough - did we hit it? */
    if (i >= n || k > n - i || t < 0) return 0;  /* PRUNE: impossible from here */
    return ksum(a, n, i+1, k-1, t - a[i])        /* include a[i] */
        || ksum(a, n, i+1, k,   t);              /* exclude a[i] */
}

Key points:

• The symmetry step is both a speed-up and an overflow guard.
• || short-circuits, so a successful include branch skips the exclude branch entirely.
• The t < 0 prune assumes non-negative elements; drop it if negatives are allowed.

Lesson

Combinations C(n,k) come from Pascal's identity C(n,k)=C(n-1,k-1)+C(n-1,k) (computed fast multiplicatively). Backtracking then enumerates subsets — here counting size-k subsets that hit a target sum by trying include/exclude at each element.

Code examples

#include <stdio.h>
static long long choose(int n,int k){ if(k<0||k>n) return 0; if(k>n-k) k=n-k; long long r=1; for(int i=0;i<k;i++) r=r*(n-i)/(i+1); return r; }
static int ksum(const int*a,int n,int i,int k,int t){ if(k==0) return t==0; if(i>=n||k>n-i||t<0) return 0; return (t>=a[i]?ksum(a,n,i+1,k-1,t-a[i]):0) + ksum(a,n,i+1,k,t); }
int main(void){
    printf("C(52,5) poker hands = %lld\n", choose(52,5));
    int a[]={1,2,3,4,5};
    printf("size-2 subsets of {1..5} summing to 5 = %d\n", ksum(a,5,0,2,5));
    return 0;
}

Line by line

Common mistakes

Naive Pascal recursion is exponential; forgetting the size constraint in the subset search.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow in a naive factorial-based binomial; the multiplicative form avoids most of it.
• No warning for missing prunes — the symptom is only slowness.

Runtime symptoms:

• choose returns a wrong or negative value. You computed n!/(k!(n-k)!) directly — the factorials overflow long before the result would. Use the multiplicative loop.
• Non-integer or truncated results. You divided before multiplying, or reordered the operations. r * (n-i) / (i+1) is exact only in that order.
• The search takes forever. The prunes are missing; k > n-i in particular removes vast subtrees.
• Search returns 1 when it should not. The k == 0 base case must also check t == 0; returning 1 unconditionally accepts any selection of the right size.
• Wrong with negative numbers. The t < 0 prune is invalid when elements can be negative.

Technique: verify choose against a Pascal's-triangle row (1, 5, 10, 10, 5, 1) and the search against small hand-checkable arrays.

Memory safety

• Intermediate overflow in the multiplicative form. r * (n - i) can overflow even when the final C(n,k) fits. Apply the symmetry reduction, use long long (or __int128), and bound n.
• Never compute binomials via factorials in fixed-width integers — 21! already overflows 64 bits, so the intermediate values are unusable long before the answer is.
• Recursion depth in the search is at most n, so the stack is fine; the cost is exponential time without pruning.
• Index bounds. The i >= n check must come before a[i] is read, or the include branch reads past the end of the array.
• Prune assumptions. t < 0 is only valid for non-negative inputs; applying it to arrays containing negatives silently discards valid solutions.
• const int *a documents that the search does not modify the input.

Real-world uses

Concrete uses: Binomial coefficients appear in probability, statistics (binomial distribution), hash-collision analysis, and combinatorial sizing. Include/exclude search underlies feature selection, team or portfolio selection under constraints, and test-case generation. The pruning discipline transfers directly to branch-and-bound optimisation.

Professional best practices:

Beginner:

• Use the multiplicative form with the symmetry reduction; never factorials.
• Add prunes one at a time and observe the runtime drop.

Intermediate:

• Compute the size of the search space first (C(n,k)); if it is astronomical, switch to a DP or an approximation.
• Sort the input to enable stronger prunes (for example, if the remaining largest elements cannot reach the target, stop).
• Document the sign assumptions your prunes rely on.

Practice tasks

1. (Beginner) Binomial coefficient. Implement long long choose(int n, int k) multiplicatively with the symmetry step. Example: C(10,3) -> 120; C(5,0) -> 1; C(5,6) -> 0. Concepts: exact integer division, overflow avoidance.

2. (Beginner) Pascal's row. Print row 5 of Pascal's triangle using choose. Example: 1 5 10 10 5 1. Concepts: validating against a known table.

3. (Intermediate) k-element subset sum. Implement ksum with all four prunes. Example: {3,4,5}, k=2, t=9 -> 1; t=100 -> 0. Concepts: include/exclude search, pruning.

4. (Intermediate) Measure the pruning. Count recursive calls with and without the k > n-i prune on a 20-element array. Concepts: how much a single prune is worth.

Summary

Combinations rest on the include/exclude split: Pascal's identity C(n,k) = C(n-1,k-1) + C(n-1,k) counts them, and the same split as a recursion searches them. Compute counts multiplicatively as r = r * (n-i) / (i+1) after reducing k to min(k, n-k) — never via factorials, which overflow long before the answer does. For the search, the prunes are the algorithm: stop when enough elements are chosen, when too few remain (k > n-i), or when the target has gone negative, and remember that last one assumes non-negative inputs.

Practice with these exercises

• Binomial coefficient
• Count size-k subsets with a target sum