Step 1 of 6

Subsets and the decision tree

Some problems ask you to look at every combination of choices: every team you could pick from a squad, every set of items that fits in a bag, every route through a maze. With a fixed number of choices you could nest loops, but when the number of choices depends on the input (10 items, or 25), you can't write "one loop per item". Recursion can: each call makes one choice and hands the rest of the problem to a deeper call.

This style is called backtracking: make a choice, explore everything that follows from it, then undo the choice and try the next one. It's a depth-first walk through a tree of decisions.

Choose or skip

The simplest decision tree builds subsets. For each item there are exactly two choices: take it or skip it. With items a, b and c the tree has 3 levels of yes/no decisions and 2 × 2 × 2 = 8 leaves, one per subset:

#include <iostream>
#include <string>
#include <vector>

void print(const std::vector<std::string>& chosen) {
    std::cout << "{";
    for (std::size_t i = 0; i < chosen.size(); i++) std::cout << (i ? " " : "") << chosen[i];
    std::cout << "}\n";
}

// Decide about items[i], items[i+1], ... given what's already chosen.
void explore(const std::vector<std::string>& items, std::size_t i, std::vector<std::string>& chosen) {
    if (i == items.size()) {           // every item decided: one complete subset
        print(chosen);
        return;
    }
    chosen.push_back(items[i]);        // choice 1: take items[i]
    explore(items, i + 1, chosen);
    chosen.pop_back();                 // undo it...
    explore(items, i + 1, chosen);     // ...choice 2: skip items[i]
}

int main() {
    std::vector<std::string> items = {"a", "b", "c"};
    std::vector<std::string> chosen;
    explore(items, 0, chosen);
}

{a b c}
{a b}
{a c}
{a}
{b c}
{b}
{c}
{}

How it works

• i says which item we're deciding about. When i == items.size(), all decisions are made, and chosen holds one complete subset. That's the base case.
• The call takes items[i], explores everything below that choice, then pop_back() puts chosen back exactly as it was, so the "skip" branch starts from the same state. This undo is the heart of backtracking: one shared chosen vector is reused for the whole search instead of copying it at every step.
• The output order follows the tree: all subsets containing a come first, because "take a" is explored completely before "skip a".

How big does it get?

n items give 2ⁿ subsets: 1,024 for 10 items, about a million for 20, about a billion for 30. Backtracking is exhaustive search, so it's only practical when n is small, or when you can cut off branches early (step 3). Each extra item doubles the work.

Your turn: write subsets(v), returning every subset of v (each with its elements in their original order; the list itself can be in any order), and count_with_sum(v, target), counting the subsets whose elements add up to target (the empty subset sums to 0).

Next: Permutations