Start learning free

LESSON 350 OF 535 · BACKTRACKING

Subsets in C++: Backtracking with Skip Then Take

Practice O(n · 2n) Read the full explanation

Given a vector nums of distinct integers, return every subset of nums: every way to pick some of its numbers, from none of them (the empty subset) to all of them.

Write the numbers of each subset in the order they have in nums. Return the subsets in the order you get by deciding about the numbers one at a time, skipping before taking: every subset without nums[0] comes before every subset with it; inside each of those two groups, the subsets without nums[1] come before the ones with it, then the same for nums[2], and so on. So the empty subset always comes first, and all of nums comes last.

 

Example 1:

Input: nums = [1,2,3]
Output: [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Explanation: The first four subsets skip 1, the last four take it.
Among the first four, [] and [3] skip 2, while [2] and [2,3] take it; in each pair, the one without 3 comes first.
The last four are the same four with 1 in front.

Example 2:

Input: nums = [0]
Output: [[],[0]]
Explanation: With one number there are two subsets: without it, then with it.

Example 3:

Input: nums = [3,-1]
Output: [[],[-1],[3],[3,-1]]
Explanation: The subsets without 3 come first. The last subset is written [3,-1], in the order of nums, not sorted.

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Walk through nums one index at a time, keeping the numbers taken so far in a list current. At index i, first skip nums[i]: go on to index i + 1 with current as it is. Then take it: add it to current, go on to index i + 1, and remove it again. When the index reaches the end of nums, every number has been skipped or taken: save a copy of current. Trying skip before take gives exactly the order above. It is the same choice as when you generate binary strings: a subset is a string of n bits, 0 for skip and 1 for take, and the subsets come out in the order of those strings.

There are 2n subsets and copying one takes up to n steps, so the time is O(n · 2n). Besides the answer, the extra space is O(n): the subset being built and one call per index.

STEP 1 OF 11
    Ctrl + Enter to check

    C++ · BACKTRACKING

    Subsets in C++, explained

    Problem overview

    The function subsets receives a vector<int> named nums of distinct integers and returns every subset of it, from the empty subset to nums itself, as a vector<vector<int>>. Inside each subset the numbers keep the order they have in nums.

    The order of the subsets is fixed too. The numbers are decided one at a time, skipping before taking: every subset without nums[0] comes before every subset with it, and inside each of those groups the subsets without nums[1] come before the ones with it, and so on.

    For nums = {1, 2, 3} the answer is:

    [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

    The first four subsets skip 1 and the last four take it. Among the first four, [] and [3] skip 2, while [2] and [2,3] take it. For {0} the answer is [[],[0]], and for {3, -1} it is [[],[-1],[3],[3,-1]]: the last subset is written in the order of nums, not sorted.

    Approach: skip or take, one number at a time

    A subset is a series of yes-or-no decisions, one per number: is this number in or out? With n numbers there are 2^n series, so the answer has exactly that many subsets, and any solution has to build all of them. The question is how to produce each decision series once, in the required order.

    Backtracking does it with recursion. Keep a vector current with the numbers taken so far, and a call that decides about index i:

    • If i has reached the end of nums, every number has been decided, and current is a finished subset. Save a copy.
    • Otherwise, first skip nums[i]: go on to i + 1 with current unchanged.
    • Then take it: add it to current, go on to i + 1, and remove it again.

    The removal is the "back" in backtracking. When the call that took nums[i] returns, current has to look as it did when the call started, because the caller carries on with it.

    Trying skip before take gives the order the statement wants: the whole skip branch, with all its subsets, is finished before the take branch starts. The order is the same as counting in binary with 0 for skip and 1 for take, with the first number as the leftmost bit.

    Step by step

    1. Create result, an empty vector<vector<int>>. Each subset is a list of numbers, so the result holds lists.
    2. Create current, an empty vector<int>: the subset being built. Nothing is taken at the start.
    3. Start the search with backtrack(nums, 0, current, result). Index 0 is the first number to decide about, and the helper adds every subset that completes what it gets.
    4. Return result. The helper added to this same vector, so it now holds everything.
    5. Declare the helper backtrack inside the class, returning void, with nums, the index i, current and result. The vectors are passed by reference so that every call sees and changes the same ones.
    6. Check for the end: if i == nums.size(), no number is left to decide about.
    7. Save and return. result.push_back(current) stores a copy of current, so the subset stays in result while current goes on changing.
    8. Skip first: call backtrack with i + 1, leaving current alone. This finds every subset that doesn't contain nums[i].
    9. Take: push_back the number onto current. Numbers are added in index order, so each subset keeps the order of nums.
    10. Recurse again with i + 1. This call finds every subset that contains nums[i].
    11. Undo: current.pop_back() removes the number, so current is what this call received.

    The solution in C++

    class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

    void backtrack(vector<int>& nums, int i, vector<int>& current, vector<vector<int>>& result) {
        if (i == nums.size()) {
            result.push_back(current);
            return;
        }
        backtrack(nums, i + 1, current, result);
        current.push_back(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.pop_back();
    }
};

    The C++ details worth a closer look:

    • References for the shared state. current and result are passed as vector<int>& and vector<vector<int>>&. Without the & each call would work on its own copy: result would stay empty in the caller, and copying would cost extra time at every call.
    • push_back copies. result.push_back(current) makes a new vector inside result with the current contents. Later push_back and pop_back calls on current don't touch the saved subsets.
    • i == nums.size() compares an int with an unsigned value. Here i is never negative, so the comparison is correct, though some compilers warn about the mix.
    • The empty subset. The first subset saved is the one where every number was skipped, and current is empty at that moment, so [] comes first without any special case.
    • Members calling members. subsets calls backtrack, which is declared below it. Inside a class definition the order of member functions doesn't matter.

    Complexity

    Time: O(n · 2^n). There are 2^n subsets, and saving each one copies up to n numbers. The recursion itself makes fewer than 2^(n + 1) calls, each doing constant work apart from the copy at the end.

    Space: O(n) extra. Besides the answer, the program holds current, at most n numbers, and one call per index on the stack, so the recursion is at most n + 1 calls deep.

    Edge cases and common mistakes

    • Forgetting pop_back(). The taken number stays in current for the rest of the search. For {1, 2, 3} the first calls then produce [[],[3],[3,2],[3,2,3],[3,2,3,1],[3,2,3,1,3],[3,2,3,1,3,2],[3,2,3,1,3,2,3]], which has repeated numbers and the wrong subsets.
    • Taking before skipping. The subsets are all there, but in a different order, so the lesson's tests fail. The skip call has to come first.
    • Passing current by value. If the helper takes vector<int> current without the &, the undo isn't needed, because every call changes its own copy. The answer is correct, but every call copies the vector, which is extra work.
    • Saving at the wrong moment. Saving a subset at every call, instead of only when i reaches the end, gives duplicates.
    • Sorting the subsets' numbers. Every subset keeps the order of nums: {3, -1} gives [3,-1], not [-1,3].
    • One number. {0} gives [[],[0]]: two subsets, the empty one first.
    • The biggest input. With 10 numbers the answer has 1,024 subsets. The first one is [], and the last one is all of nums.

    Testing

    • nums = {1, 2, 3} gives [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]].
    • nums = {0} gives [[],[0]].
    • nums = {3, -1} gives [[],[-1],[3],[3,-1]].
    • nums = {5, 4, 3, 2, 1, 0, -1, -2, -3, -4} gives 1,024 subsets, the first [] and the last [5,4,3,2,1,0,-1,-2,-3,-4].
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free