Subsets and permutations

Generate every subset and every ordering of a list by deciding one item at a time and undoing each decision afterwards. The same pattern, with a check that cuts off hopeless branches, finds the subsets with a given sum.

Subsets	Permutations	Subset sum (with pruning)	Extra space
\(O(n \cdot 2^n)\)	\(O(n \cdot n!)\)	at most \(O(2^n)\), often far less	\(O(n)\) besides the output

The idea

Subsets. Each item is either out or in: two choices per item, \(2^n\) subsets. Picture a tree: the root has decided nothing; each level decides one item; each of the \(2^n\) leaves is one subset. A recursive function walks this tree: decide item \(i\) (first "out", then "in"), recurse to item \(i + 1\), and when all items are decided, record the subset.

Permutations. Fill position 1 with any of the \(n\) items, position 2 with any of the \(n - 1\) left, and so on: \(n!\) orderings. A used list says which items are still free.

Subset sum. Look for the subsets that add up to a target. With positive numbers, once the running total is above the target, nothing deeper can work, so return at once: pruning.

How it works

• Subsets: go(i): if i == n, record chosen. Otherwise go(i + 1); append items[i]; go(i + 1); pop.
• Permutations: go(): if chosen is full, record it. Otherwise for each unused item: mark it, append, go(), pop, unmark.
• Subset sum: like subsets, carrying the running total, and returning when it equals the target (record) or passes it (prune).

Code

PythonJavaC++

def subsets(items):
    """Every subset: for each item, first leave it out, then put it in."""
    out, chosen = [], []

    def go(i):
        if i == len(items):
            out.append(list(chosen))
            return
        go(i + 1)                            # without items[i]
        chosen.append(items[i])              # choose
        go(i + 1)                            # with items[i]
        chosen.pop()                         # un-choose (the "back" in backtracking)
    go(0)
    return out


def permutations(items):
    """Every ordering: fill the positions one by one with an item not used yet."""
    out, chosen, used = [], [], [False] * len(items)

    def go():
        if len(chosen) == len(items):
            out.append(list(chosen))
            return
        for i, x in enumerate(items):
            if not used[i]:
                used[i] = True; chosen.append(x)
                go()
                chosen.pop(); used[i] = False
    go()
    return out


def subset_sums(items, target):
    """Every subset (keeping the items' order) that adds up to target; all items positive.
    Prunes: stop as soon as the running sum is too big."""
    out, chosen = [], []

    def go(i, total):
        if total == target:
            out.append(list(chosen))
            return
        if i == len(items) or total > target:   # nothing left, or already too much: give up on this branch
            return
        chosen.append(items[i])
        go(i + 1, total + items[i])
        chosen.pop()
        go(i + 1, total)
    go(0, 0)
    return out


if __name__ == "__main__":
    print(subsets([1, 2, 3]))
    print(permutations([1, 2, 3]))
    print(subset_sums([3, 34, 4, 12, 5, 2], 9))

import java.util.ArrayList;
import java.util.List;

public class SubsetsPermutations {
    static List<List<Integer>> out;
    static List<Integer> chosen;

    /** Every subset: for each item, first leave it out, then put it in. */
    static List<List<Integer>> subsets(int[] items) {
        out = new ArrayList<>(); chosen = new ArrayList<>();
        subsetsGo(items, 0);
        return out;
    }

    static void subsetsGo(int[] items, int i) {
        if (i == items.length) { out.add(new ArrayList<>(chosen)); return; }
        subsetsGo(items, i + 1);                      // without items[i]
        chosen.add(items[i]);                         // choose
        subsetsGo(items, i + 1);                      // with items[i]
        chosen.remove(chosen.size() - 1);             // un-choose (the "back" in backtracking)
    }

    /** Every ordering: fill the positions one by one with an item not used yet. */
    static List<List<Integer>> permutations(int[] items) {
        out = new ArrayList<>(); chosen = new ArrayList<>();
        permGo(items, new boolean[items.length]);
        return out;
    }

    static void permGo(int[] items, boolean[] used) {
        if (chosen.size() == items.length) { out.add(new ArrayList<>(chosen)); return; }
        for (int i = 0; i < items.length; i++)
            if (!used[i]) {
                used[i] = true; chosen.add(items[i]);
                permGo(items, used);
                chosen.remove(chosen.size() - 1); used[i] = false;
            }
    }

    /** Every subset (keeping the items' order) that adds up to target; all items positive.
     *  Prunes: stop as soon as the running sum is too big. */
    static List<List<Integer>> subsetSums(int[] items, int target) {
        out = new ArrayList<>(); chosen = new ArrayList<>();
        sumGo(items, target, 0, 0);
        return out;
    }

    static void sumGo(int[] items, int target, int i, int total) {
        if (total == target) { out.add(new ArrayList<>(chosen)); return; }
        if (i == items.length || total > target) return;   // nothing left, or already too much
        chosen.add(items[i]);
        sumGo(items, target, i + 1, total + items[i]);
        chosen.remove(chosen.size() - 1);
        sumGo(items, target, i + 1, total);
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
        System.out.println(permutations(new int[]{1, 2, 3}));
        System.out.println(subsetSums(new int[]{3, 34, 4, 12, 5, 2}, 9));
    }
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

using List = vector<vector<int>>;

// Every subset: for each item, first leave it out, then put it in.
void subsetsGo(const vector<int>& items, size_t i, vector<int>& chosen, List& out) {
    if (i == items.size()) { out.push_back(chosen); return; }
    subsetsGo(items, i + 1, chosen, out);            // without items[i]
    chosen.push_back(items[i]);                      // choose
    subsetsGo(items, i + 1, chosen, out);            // with items[i]
    chosen.pop_back();                               // un-choose (the "back" in backtracking)
}

// Every ordering: fill the positions one by one with an item not used yet.
void permGo(const vector<int>& items, vector<bool>& used, vector<int>& chosen, List& out) {
    if (chosen.size() == items.size()) { out.push_back(chosen); return; }
    for (size_t i = 0; i < items.size(); i++)
        if (!used[i]) {
            used[i] = true; chosen.push_back(items[i]);
            permGo(items, used, chosen, out);
            chosen.pop_back(); used[i] = false;
        }
}

// Every subset (keeping the items' order) that adds up to target; all items positive.
// Prunes: stop as soon as the running sum is too big.
void sumGo(const vector<int>& items, int target, size_t i, int total, vector<int>& chosen, List& out) {
    if (total == target) { out.push_back(chosen); return; }
    if (i == items.size() || total > target) return;   // nothing left, or already too much
    chosen.push_back(items[i]);
    sumGo(items, target, i + 1, total + items[i], chosen, out);
    chosen.pop_back();
    sumGo(items, target, i + 1, total, chosen, out);
}

string show(const List& L) {
    string s = "[";
    for (size_t k = 0; k < L.size(); k++) {
        s += k ? ", [" : "[";
        for (size_t j = 0; j < L[k].size(); j++) s += (j ? ", " : "") + to_string(L[k][j]);
        s += "]";
    }
    return s + "]";
}

int main() {
    vector<int> chosen;
    List out;
    subsetsGo({1, 2, 3}, 0, chosen, out);
    cout << show(out) << "\n";
    out.clear();
    vector<bool> used(3, false);
    permGo({1, 2, 3}, used, chosen, out);
    cout << show(out) << "\n";
    out.clear();
    sumGo({3, 34, 4, 12, 5, 2}, 9, 0, 0, chosen, out);
    cout << show(out) << "\n";
}

Output: the 8 subsets of [1, 2, 3], starting with the empty one; the 6 permutations in dictionary order; and [[3, 4, 2], [4, 5]], the two subsets of [3, 34, 4, 12, 5, 2] that add up to 9.

When to use it

• Trying every combination when \(n\) is small (up to about 20–25 for subsets, 10–11 for permutations).
• Brute-force checks of a cleverer algorithm on small inputs: generate all cases and compare.
• Puzzles and planning: choosing a team, ordering stops on a route (the travelling salesman for a few cities), assigning tasks.
• With pruning, much larger inputs can still be searched when the rules cut most branches.

Common mistakes

• Recording the shared list itself instead of a copy: every recorded answer then changes as the search continues, and they all end up empty.
• Forgetting to undo (pop, used[i] = False): later branches see a wrong state.
• Pruning on a sum with negative numbers: the total can come back down, so "too big" does not mean hopeless.
• Duplicates in the input: [1, 1, 2] would give repeated subsets and permutations; sort and skip an item equal to the previous one at the same level.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: subsets of [1, 2, 3] and the sum 9

The order the subsets come out (0 = out, 1 = in, for items 1, 2, 3):

Decisions	Subset
0 0 0	{}
0 0 1	{3}
0 1 0	{2}
0 1 1	{2, 3}
1 0 0	{1}
1 0 1	{1, 3}
1 1 0	{1, 2}
1 1 1	{1, 2, 3}

The decisions count from 0 to 7 in binary: subsets of \(n\) items and \(n\)-bit numbers are the same thing.

Subset sum 9 from [3, 34, 4, 12, 5, 2]: take 3; take 34 → 37 > 9, prune; skip 34; take 4 → 7; take 12 → 19, prune; skip 12; take 5 → 12, prune; skip 5; take 2 → 9, found [3, 4, 2]. Later, skipping 3: ... take 4, skip 12, take 5 → 9, found [4, 5].

The math: counting, and the cost of listing

Counting. Each item has 2 choices independently, so there are \(2^n\) subsets; \(\sum_k \binom{n}{k} = 2^n\) groups them by size. Orderings: \(n\) choices for the first position, \(n - 1\) for the second, ..., so \(n! = n(n-1)\cdots 1\).

Tree size. The subset tree has \(2^{n+1} - 1\) nodes. The permutation tree has \(\sum_{k=0}^{n} \frac{n!}{(n-k)!} = n! \sum_{j=0}^{n} \frac{1}{j!} < e \cdot n!\) nodes.

Time. Each answer costs \(O(n)\) to copy, so listing all subsets is \(\Theta(n \, 2^n)\) and all permutations \(\Theta(n \cdot n!)\). No algorithm can list them faster than the size of its output.

How fast these grow. \(2^{30} \approx 10^9\); \(10! = 3{,}628{,}800\); \(13! \approx 6.2 \times 10^9\); \(20! \approx 2.4 \times 10^{18}\). Stirling's formula: \(n! \approx \sqrt{2\pi n}\,(n/e)^n\).

Subset sum is NP-complete, so no polynomial algorithm is known; with small numbers, the knapsack-style DP solves it in \(O(n \cdot \text{target})\).

Watch it step by step

The tree of decisions for {1, 2, 3}: a left branch leaves the item out, a right branch (+k) puts it in. Red is where the search is, green has been visited, purple are the subsets found.

Variations and related ideas

• Bitmasks: loop mask from 0 to \(2^n - 1\); bit \(i\) says whether item \(i\) is in. Short and fast for \(n \le 20\) or so.
• Next permutation: step from one ordering to the next in dictionary order without recursion (std::next_permutation in C++).
• Combinations (subsets of exactly \(k\) items): stop going deeper once \(k\) are chosen, or when too few items remain.
• Gray code: list subsets so that consecutive ones differ by one item.
• Heap's algorithm: each permutation from the previous by a single swap.
• Meet in the middle: for subset sum with \(n \approx 40\), list the \(2^{20}\) sums of each half and match them.

See also

• N-Queens
• Recursion
• 0/1 knapsack

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Combinatorial Algorithms, Part 1, Section 7.2.1 (generating all possibilities).
• S. S. Skiena, The Algorithm Design Manual, 3rd ed., Springer, 2020, Chapter 9 (combinatorial search).