Subsets

Backtracking O(2^n) O(n)

Generates every subset of a set by, for each element, branching into taking it or leaving it out.

building

{1}

recorded (0)

none yet

Set: 1, 2, 3 · found 0 / 8

1/22

Include 1.

InvariantThe current list is a decision made for each of the first i elements: in or out.

choosebacktrackrecorded

subsets.c

void subsets(int a[], int n, int i, int cur[], int k) {
    if (i == n) {
        printSubset(cur, k);
        return;
    }
    cur[k] = a[i];              /* include a[i] */
    subsets(a, n, i + 1, cur, k + 1);
    /* backtrack: exclude a[i] */
    subsets(a, n, i + 1, cur, k);
}

How Subsets works

For every element make a binary decision: in or out. The recursion tree has 2ⁿ leaves — each leaf is exactly one subset.

When to use it

Enumerating all combinations for brute-force checks, power sets, feature subsets.