Subsets and the include or exclude choice

Why it matters

"Generate all combinations" is the entry point to backtracking. Backtracking is the family of methods that try a choice, follow it as far as it goes, and then undo the choice to try the next one. Subsets are the simplest place to learn it, because every item has exactly two options. Once you can list all subsets of a small set, you can solve many interview problems with small changes: subsets with a given sum, combinations of a fixed size, subsets with no duplicates, and the partition problems used in planning tools.

The idea: in or out, for every item

A subset of a set is any selection of its items. It can be empty, it can be the whole set, and it can be anything in between. The order inside a subset does not matter, so {1, 2} and {2, 1} are the same subset.

Count how many subsets a set has. Take the set {1, 2, 3}. For item 1 there are two choices: in or out. For item 2 there are two more choices, and for item 3 two more. Each item doubles the count, so the total is 2 times 2 times 2, which is 8. A set with n items has 2 to the power n subsets. This includes the empty subset, which is always one of the answers.

Think of packing a bag for a short trip. You have three things on the table: a book, a charger and a jacket. For each one you decide, pack it or leave it. The eight possible bags are the eight subsets. If you want to list every bag you could pack, you walk through the decisions in a fixed order and write down each finished bag.

The decisions form a tree. The root is the start, before any decision. Each node has two children, one for "include this item" and one for "skip this item". Each leaf, the end of a path, is one finished subset. Here is the tree for {1, 2}:

                 start
          /                \
     include 1           skip 1
        [1]                 []
       /    \              /    \
 include 2  skip 2    include 2  skip 2
   [1,2]     [1]        [2]       []

The leaves are the bottom row, and each leaf holds one subset. The picture below shows the tree for three items, and the code in this lesson walks it in exactly this order.

Decision tree for the subsets of one, two and three: each node splits into include and skip

Recursion matches the tree

The decision tree is a recursive shape. At position i in the list, the function makes two calls: one with item i included, and one with item i skipped. Each call works on position i + 1, which is a smaller problem. The base case is i == n, which means every item has been decided. At that point the current selection is one finished subset, and the function prints it or saves it.

The current selection needs a home. The function keeps a vector called cur that holds the items chosen so far. Include means cur gets the item added. Skip means cur is left alone. When the function reaches the base case, cur holds one subset.

The code, step by step

The first program lists every subset of {1, 2, 3}. Read the three commented lines in the middle of the function first. They are the heart of backtracking, and they come back in every lesson of this module.

No input is needed. The output is:

{1,2,3}
{1,2}
{1,3}
{1}
{2,3}
{2}
{3}
{}

Trace the first three lines of output. The first leaf is reached by including every item. cur goes [], then [1], then [1, 2], then [1, 2, 3]. At the base case the function prints {1,2,3}. Then it returns up one level, which is the call that decided item 3. That call had already included 3, so it runs pop_back() and cur becomes [1, 2]. The next call, which skips 3, prints {1,2}. This is the moment that shows the undo step at work. Without the pop_back(), cur would still hold 3 when the skip branch ran, and the output would be wrong.

After both branches of the item-2 decision finish, the call for item 1 undoes its choice. It removes 1 from cur, which leaves an empty vector, and then it runs the skip branch for item 1. The rest of the output follows the same pattern. Every line starts with the include branch and then the skip branch, so the output is in a fixed order: first the subsets that contain 1, then the subsets that do not.

Study the order carefully. Interviewers often ask for the output in a given order, and the include-first order here is a choice. If you skip first and include second, every subset comes out in the reverse order of the branches, and the printed list is different even though the set of subsets is the same.

Choose, explore, un-choose

The three commented lines are the pattern. It has three steps.

1. Choose. Make one decision and change the shared state to reflect it. Here the state is cur, and the choice is to add a[i].
2. Explore. Recurse to decide the rest, using the changed state.
3. Un-choose. Undo the change from step 1, so the state is exactly as it was before the choice. This is the backtrack.

The undo is the step beginners forget. cur is passed by reference, so every call in the whole tree shares one vector. When the include branch returns, cur still contains the item it added. If the code went straight to the skip branch, that item would leak into every subset created afterward. The pop_back() removes it. Because each branch restores the state before the next one starts, the tree is walked correctly with only one shared vector.

Compare this with passing cur by value. Each call would get its own copy, so nothing would leak and no undo would be needed. The output would still be correct. But each call would copy the whole vector, which costs time. The reference style is faster, and it is the style you should use in interviews. The price is the discipline of always undoing.

Here is the same tree walked with a visualizer. Each node of the decision tree has two children, which is the shape the tree-traversal animation walks through. Step through it and match each visited node to a line of the output.

Collecting the results

Printing is fine for learning, but most real problems ask for the subsets as data. Your function should return them, so that other code can use them. The next program collects each finished subset into a vector<vector<int>>. It pushes a copy of cur at each leaf. The copy is important, because cur keeps changing after the push.

No input is needed. The output is:

count 4
[5 6]
[5]
[6]
[]

The first leaf is [5 6] and the last is the empty subset, as before. The function is called with the temporary vector {5, 6}, which is passed as a const reference. That works because a const reference can bind to a temporary. If you change the parameter to a plain vector<int>&, the call fails to compile, and you will see the message in the mistakes section below.

The for (const vector<int>& s : out) loop reads each subset without copying it. The const promises that the loop does not change the subset. Use this form for read-only loops over large data.

Worked example: count the subsets with a given sum

Subsets are useful when you want to test a property. Here is a classic problem. Given some numbers and a target, count the subsets whose sum equals the target. Each subset is a leaf of the tree, so the function counts leaves that pass the test. Instead of carrying cur, the function carries a running sum.

Type this into the Input box and press Run:

4
1 2 3 4
5

The output is:

count = 2

Only two subsets of {1, 2, 3, 4} sum to 5: {1, 4} and {2, 3}. The program finds them by visiting all 16 leaves. Notice that this version does not need to undo anything. It passes the running sum as a value, so each branch gets its own copy. That is the trade-off the earlier section described: passing values is simpler, and it does not need an undo, but it works only when the state is one small number. A vector that changes in many ways would need the choose-explore-undo pattern.

Trace a small branch of the tree. Start with countSum(a, 0, 0, 5). The include branch passes sum 1 down. Then the include branch for item 2 passes sum 3, and the include branch for item 3 passes sum 6. Item 4 is then considered, and whether it is included or skipped, the sum does not come out to 5 along that path. The skip branch for item 3 passes sum 3 with item 4 still left, and including 4 gives 7 while skipping gives 3. Neither hits 5, so that path contributes zero. The count builds up as the leaves return their 1s and 0s.

Here is a useful improvement for interviews. If the sum already exceeds the target and every number is positive, you can stop early. That is pruning, which you will meet in the next lesson. The code above is simpler, and it is correct even with negative numbers, which is why it does not prune.

Worked example: all subsets of a string

Subsets work on any sequence, including strings. The only change is that cur becomes a string and the output shows each subset in brackets. The empty subset prints as [].

The output is:

[abc]
[ab]
[ac]
[a]
[bc]
[b]
[c]
[]

The order is the same as the vector version, because the decision tree is the same. Item a is decided first, then b, then c. Each finished string is one subset, and cur is a string, so push_back and pop_back work the same way. The string version is a good example of how a pattern carries over to any container: only the names change.

Combinations of a fixed size

A combination is a subset of a fixed size. Choosing 2 friends from 4 is a combination. Its order does not matter, so {1, 2} and {2, 1} count once. This problem uses the same tree, with one extra rule: stop as soon as cur has k items, and prune any branch that cannot reach size k.

Type this into the Input box and press Run:

4 2

The output is:

1 2
1 3
1 4
2 3
2 4
3 4

The pruning line is the new idea. Suppose you have chosen nothing yet, you need 2 numbers, and only 1 number is left, which happens at i == 4 for n equal to 4. The check (n - i + 1) < k - size compares what is left, 1 number, with what is needed, 2. It is less, so the branch is dropped. Without pruning the function would still find the right answers, but it would explore dead branches.

Notice that the numbers are visited from 1 upward, so the first combination is 1 2, and the output is in lexicographic order. Lexicographic order means dictionary order, comparing the first number and then the second. Sorting the output that way is free when the input is visited in order.

The animation above shows a recursion stack. For the combinations program, watch how the stack gets to depth k and then returns, as each combination is printed at the bottom of its path.

What happens inside the computer

Each call to subsets is a frame on the call stack, as you saw in the first lesson of this module. The frame holds i, the reference to a and the reference to cur. The references are just addresses, so they cost only a few bytes each. The vector cur lives in one place in memory, outside any frame, and every frame points to it.

When cur.push_back(a[i]) runs, the vector may need more space in memory. A vector keeps its elements in one block. If the block is full, the vector allocates a bigger block, copies the elements and frees the old one. The pointers into the vector are then no longer valid, which is one reason you should never store a reference to cur. The pop_back() does not free memory. It only makes the vector's size smaller, so a later push reuses the space.

This is why the copy in collect matters. out.push_back(cur) copies the contents of cur into a new vector inside out. The new vector has its own memory, so later changes to cur do not affect it.

Complexity

Let n be the number of items.

• There are 2 to the power n leaves, one per subset.
• Each leaf that is printed or copied costs up to n steps, because a subset can hold up to n items. Printing or copying every subset costs O(n times 2 to the power n) in total.
• The number of internal nodes is also about 2 to the power n, so the walk visits about twice as many nodes as there are leaves.
• The stack depth is n, so the extra space used by the recursion itself is O(n). The output space is O(n times 2 to the power n) when you save every subset.
• The countSum version does not store subsets, so its extra space is O(n), and its time is still about 2 to the power n, because every leaf is visited.

Be ready for the question "why is this exponential?" Answer that every item doubles the number of possible answers, so no algorithm can list them all faster than the number of answers. The answer count is the lower bound.

What the output order tells you

The order of the subsets depends only on the order of the decisions. Include first gives one order, and skip first gives the reverse. A problem that asks you to return subsets in lexicographic order is solved by visiting the items in sorted order and deciding the lower item first. Practice changing the order by swapping the two recursive calls, and predict the output before you run it. Being able to predict an order is a good sign that you understand the tree.

The tree as a table

Sometimes a table is easier to read than a tree. Each row below is one leaf of the tree for {1, 2, 3}. The first three columns record the decision for each item, and the last column is the subset those decisions produce.

Read the first three columns as a binary number, with "in" as 1 and "out" as 0. The rows count down from 111 to 000, which is 7 down to 0. Each row is one number, and each number is one subset, because its bits say which items to keep. That link between subsets and binary numbers gives a second way to list them.

Subsets with bits, and no recursion

Because each item is in or out, a subset can be stored as a whole number. Bit i of the number says whether item i is in the subset. Then you can list every subset with a plain loop over the numbers from 0 up to 2 to the power n minus 1. For each number, print the items whose bit is set.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {1, 2, 3};
    int n = a.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        cout << "{";
        bool first = true;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                if (!first) cout << ",";
                cout << a[i];
                first = false;
            }
        }
        cout << "}\n";
    }
    return 0;
}

The shift 1 << i makes a number with only bit i set, so mask & (1 << i) tests that one bit. The loop prints the subsets in the order of their numbers, which is different from the include-first order of the recursion. This method uses O(1) extra memory beyond the output, and its time is still O(n times 2 to the power n). Recursion is the method to explain in an interview, but the bit method is the one many production programs use, so it is worth knowing both.

Why there are 2 to the power n leaves

A short proof by induction shows why the count is exactly 2 to the power n. With no items there is one subset, the empty one, so the count is 1, which is 2 to the power 0. Suppose a set of k items has 2 to the power k subsets. Add one new item x. Each old subset can appear without x, or with x added, so the new count is twice the old one, which is 2 times 2 to the power k. That equals 2 to the power k plus 1, which is the statement for k plus 1.

The recursion in this lesson mirrors that proof. The base case is the empty set, and each item doubles the number of leaves below it.

What to say out loud in an interview

When an interviewer asks for all subsets, a strong answer follows four steps. First, name the pattern: each item is in or out, so this is a binary decision tree. Second, state the base case and the count: there are 2 to the power n leaves, so the output is at least that big. Third, state the undo: add the item, recurse, then remove it, so the shared list stays correct. Fourth, state the complexity: time is O(n times 2 to the power n), dominated by copying the output.

A common follow-up is "How would you handle duplicate values?" The answer is to sort the input and skip equal values at the same level, as shown in the variations section. Practice saying the four steps until they come out without pauses.

Trace one branch, call by call

Walk the first part of subsets for {1, 2} slowly. Each numbered line is one call, with the value of i and the content of cur when the call starts.

1. subsets(i=0, cur=[]). Item 1 is included, so cur becomes [1].
2. subsets(i=1, cur=[1]). Item 2 is included, so cur becomes [1, 2].
3. subsets(i=2, cur=[1, 2]). i equals the size, so this call prints {1,2} and returns.
4. Back in call 2, pop_back removes the 2, so cur is [1]. The skip branch runs.
5. subsets(i=2, cur=[1]). This call prints {1} and returns.
6. Back in call 1, pop_back removes the 1, so cur is []. The skip branch for item 1 runs.
7. subsets(i=1, cur=[]). Item 2 is included, so cur becomes [2].
8. subsets(i=2, cur=[2]). This call prints {2} and returns.
9. Back in call 7, pop_back removes the 2. The skip branch runs.
10. subsets(i=2, cur=[]). This call prints {} and returns.

The printed lines are {1,2}, {1}, {2} and {}. Notice that cur is empty at the start of call 7, and again at the start of call 10. That is the invariant of backtracking: when a branch returns, the shared state is exactly what it was when the branch started. If you can state that rule for each call, you can predict the output of any backtracking function, and you can spot the call where the rule breaks when a bug appears.

Common mistakes and the messages you will see

Mistake 1: forgetting pop_back(). The program compiles and runs, but the subsets are wrong. Items leak from one branch into the next. In the printed output you see subsets that contain numbers they should not, such as {1,2,3} appearing where it should not. The fix is the undo line.

Mistake 2: storing a reference to cur. If you write out.push_back(cur) you copy, which is correct. If you try to keep a pointer or a reference to cur, the stored thing changes as cur changes, and every saved subset ends up equal to whatever cur holds at the end, which is the empty vector. The fix is to copy.

Mistake 3: passing a temporary to a non-const reference. A common compile error comes from calling collect({5, 6}, 0, cur, out) when the first parameter is a plain reference. The function collect takes const vector<int>& for the input, which accepts a temporary. If you write vector<int>& a, g++ stops with this message:

error: cannot bind non-const lvalue reference of type 'std::vector<int>&' to an rvalue of type 'std::vector<int>'

The message means you asked to change something that is only a temporary, which is not allowed. The fix is const for read-only input.

Mistake 4: wrong number of arguments. If you call subsets(a, cur) and forget the index, g++ tries to pass cur where the index belongs. It stops with this message:

error: cannot convert 'std::vector<int>' to 'int'

The note under the message says which parameter it was setting up. Read the call against the function's parameter list. The missing index is the difference.

Mistake 5: duplicates in the input. If the input contains repeated values, such as {1, 1}, the output contains the subset {1} twice. The tree treats the two 1s as different items, so it lists both. The usual interview fix is to sort the input and skip a value at the same level when it equals the value before it, as the variations section shows.

Mistake 6: wrong base case. If you print at every node instead of only at the leaves, you print more subsets than you should. Print only when i == n, which means every item has been decided.

Debugging walkthrough

A student writes the subsets program without the undo line and runs it on {1, 2}. The output is:

{1,2}
{1,2}
{1,2,2}
{1,2,2}

There are four lines, and the last two are wrong. The number 2 was added to cur and never removed, so later subsets carry an extra 2. The student adds a line to print cur before each call and sees that the state is wrong. The line that caused the trouble is the one that adds a[i] to cur but never removes it, so after the include branch finishes, the next branch starts with the extra item still present.

The buggy code, with the undo line removed, looks like this:

void subsets(const vector<int>& a, int i, vector<int>& cur) {
    if (i == (int)a.size()) { /* print cur */ return; }
    cur.push_back(a[i]);
    subsets(a, i + 1, cur);
    subsets(a, i + 1, cur);       // bug: pop_back is missing
}

The fix is to add cur.pop_back(); between the two recursive calls. The method for finding this kind of bug is to print the state at each call and check that it returns to where it started after each choice. For backtracking, that is the most important property to test.

Variations and edge cases

Empty input. An empty set has exactly one subset, the empty one. Your base case handles it, because the function reaches i == n at once and prints {}. Check this case first in any test.

Subsets with a limit on size. Stop the recursion early when cur reaches the limit, as the combinations program does. This is pruning, and it makes the walk smaller.

Subsets without duplicates. Sort the input. In the loop version of subsets, which picks a next item at each level instead of deciding one item at a time, skip a value when it equals the value before it at the same level. Here is the idea as a plain fragment:

void subsetsDedup(vector<int>& a, int start, vector<int>& cur, vector<vector<int>>& out) {
    out.push_back(cur);
    for (int i = start; i < (int)a.size(); i++) {
        if (i > start && a[i] == a[i - 1]) continue;   // same value at same level
        cur.push_back(a[i]);
        subsetsDedup(a, i + 1, cur, out);
        cur.pop_back();
    }
}

This version records each subset when it is first created, not only at the leaves. It is a different tree shape from the include and skip tree, but the same undo idea applies.

Subsets with a target sum and negative numbers. Pruning on a sum works only when every number is positive. With negative numbers, adding a value can lower the sum again, so a branch that looks too big may still come back to the target. The countSum program in this lesson does not prune for that reason.

Interview questions

• How many subsets does a set of n distinct items have? Answer 2 to the power n, including the empty set.
• Why does the naive subset generation take exponential time? Answer that the output size is 2 to the power n, so any method that lists them all must take at least that long.
• How do you avoid duplicates when the input has repeated values? Answer by sorting and skipping equal values at the same level.
• Why must you undo a choice in backtracking? Answer that the shared state would otherwise carry the choice into branches where it does not belong.

Real-world uses

Subsets appear in many planning tools. A shopping app that offers combinations of discounts tries subsets of coupons. A feature flag system that tests each combination of settings is working with subsets. A packing tool that asks which items fit in a bag checks subsets against a weight limit, which is the sum problem with a cap. A team that selects members for a project from a pool is choosing a subset with a fixed size, which is the combinations problem. In each case the decision tree is the same, and only the test at the leaf changes.

Practice

Write each exercise before you open the solution. Try the hint first.

1. Count the subsets of {2, 3, 5, 7} whose sum is 10. Predict the count, then run the countSum program with that input. Hint: list the subsets that sum to 10 by hand first.

2. Print all subsets of {1, 2, 3} in the skip-first order. Predict the first line before you run it.

3. Write int countSubsetsOfSize(const vector<int>& a, int i, int k) that returns how many subsets of size exactly k exist, using the include and skip shape. Test with {1, 2, 3, 4} and k equal to 2, which should give 6.

int countSubsetsOfSize(const vector<int>& a, int i, int k) {
    if (k == 0) return 1;                       // one way to pick nothing
    if (i == (int)a.size()) return 0;           // ran out of items
    return countSubsetsOfSize(a, i + 1, k - 1)  // include a[i]
         + countSubsetsOfSize(a, i + 1, k);     // skip a[i]
}

4. Explain in two sentences why out.push_back(cur) is correct and out.push_back(&cur) is not.

5. Predict whether this change is safe: move cur.pop_back() to just before the first recursive call. Explain your answer.

6. Write bool hasSubsetSum(const vector<int>& a, int i, int sum, int target) that returns true as soon as some subset sums to target, and stops searching at that point. Hint: return true from the include branch before trying the skip branch.

bool hasSubsetSum(const vector<int>& a, int i, int sum, int target) {
    if (sum == target) return true;
    if (i == (int)a.size()) return false;
    if (hasSubsetSum(a, i + 1, sum + a[i], target)) return true;
    return hasSubsetSum(a, i + 1, sum, target);
}

7. A student says that the number of printed lines is always 2 to the power n. Give a counter example with a set that has repeated values, and say what happens.

8. Write a recursive void printPower(int n, int i, string& cur) that prints every binary string of length n, from "000" to "111" in order. Hint: each position is 0 or 1, which is an include and skip choice.

void printPower(int n, int i, string& cur) {
    if (i == n) { cout << cur << "\n"; return; }
    cur.push_back('0');
    printPower(n, i + 1, cur);
    cur.pop_back();
    cur.push_back('1');
    printPower(n, i + 1, cur);
    cur.pop_back();
}

9. A combination of size 2 from {1, 2, 3, 4} is printed in order. Explain why the pruning check in the combinations program does not change the output, only the work done.

10. Count the leaves and internal nodes of the tree for 4 items. Then check your count against 2 to the power 4 and the number of nodes in the tree.

What you now know

• A set of n items has 2 to the power n subsets, because each item is in or out.
• The include and skip calls form a decision tree, and the base case is the leaf where every item has been decided.
• Backtracking is choose, explore, undo. The undo restores the shared state before the next branch.
• Copy the current state when you save a result, and never keep a reference to it.
• Pruning drops branches that cannot succeed, and it is what makes the combinations program fast.
• Sort the input and skip equal values at the same level to avoid duplicate subsets.