Start learning free

LESSON 351 OF 536 · BACKTRACKING

Subsets in Python: Backtracking with Skip and Take

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

Given a list 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 10
    Ctrl + Enter to check

    PYTHON · BACKTRACKING

    Subsets in Python, explained

    Problem overview

    The method subsets receives a list nums of distinct integers and returns every subset of it: every way to pick some of the numbers, from none (the empty subset) to all of them. Each subset keeps the order its numbers have in nums.

    The order of the subsets matters too. The method decides about the numbers one at a time, trying "skip" before "take". Every subset without nums[0] comes before every subset with it. Inside each of those groups, the subsets without nums[1] come first, and so on. The empty subset is always first and all of nums is always last.

    For nums = [1, 2, 3] the result 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. For nums = [0] the result is [[], [0]]. For nums = [3, -1] it is [[], [-1], [3], [3, -1]]: the last subset keeps the order of nums, it isn't sorted.

    Approach: one decision per number

    Each number is either in a subset or not, so building a subset is a series of yes/no decisions, one per number. With n numbers there are 2^n series of decisions, which is the number of subsets. For 10 numbers, that is 1024, and the method does return 1024 subsets for nums = [0, 1, ..., 9].

    Backtracking walks through all those decision series. Keep a list current with the numbers taken so far, and a position i that says which number to decide about next:

    1. If i is past the last number, every number has been decided. current is a finished subset, so save it.
    2. Otherwise, first skip nums[i]: continue with i + 1 and leave current as it is.
    3. Then take nums[i]: add it to current, continue with i + 1, and afterwards remove it again.

    The removal is the "back" in backtracking. When the call that took nums[i] returns, current must be exactly what the call received, so the caller can go on with its own next choice. Trying skip before take produces the order the statement asks for: the branch that skips nums[0] is explored completely before the branch that takes it, and the same holds at every deeper level.

    The same order comes from counting in binary. Write 0 for skip and 1 for take: the subsets appear in the order of the bit strings 000, 001, 010, and so on.

    Step by step

    1. Create result as an empty list. It collects the subsets, so it will be a list of lists.
    2. Start the search with self.backtrack(nums, 0, [], result): nothing is decided yet, so the index is 0 and the subset being built is empty. The helper is written next.
    3. Return result. The helper adds to this same list, so after the call it holds every subset.
    4. Declare the helper backtrack(self, nums, i, current, result) inside the class. Each call decides about nums[i] and calls itself for the next index.
    5. Check for the end. When i == len(nums), no number is left to decide about.
    6. Save a copy and return. current.copy() makes a new list with the same numbers. The copy is needed because current keeps changing as the search goes on.
    7. Skip. Call self.backtrack(nums, i + 1, current, result) without touching current. This finds every subset without nums[i].
    8. Take. Add nums[i] to the end of current with append. Numbers are added in index order, so each subset keeps the order of nums.
    9. Recurse again with the same arguments. This call finds every subset that contains nums[i].
    10. Undo. current.pop() removes the last number, which is nums[i], so current is what this call received.

    The solution in Python

    class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.backtrack(nums, 0, [], result)
        return result
    def backtrack(self, nums, i, current, result):
        if i == len(nums):
            result.append(current.copy())
            return
        self.backtrack(nums, i + 1, current, result)
        current.append(nums[i])
        self.backtrack(nums, i + 1, current, result)
        current.pop()

    Python details worth a closer look:

    • Lists are shared, not copied. Passing current to a function passes the same list object, not a duplicate. That is what lets result collect the answers, and it is also why the copy matters. If the base case appended current itself, result would hold many references to one list, and since the search ends with current empty, every entry would show it that way. For nums = [1, 2, 3] that mistake gives [[], [], [], [], [], [], [], []].
    • Forgetting the undo. Without current.pop(), the taken numbers pile up across branches. For nums = [1, 2] the result becomes [[], [2], [2, 1], [2, 1, 2]], which has the wrong subsets in the wrong order.
    • Copying a list. current.copy(), list(current) and current[:] all make a shallow copy. Here the elements are integers, so a shallow copy is all that's needed.
    • Methods and self. The helper belongs to the class, so the calls are written self.backtrack(...), and the helper's definition lists self first.
    • Recursion depth. The recursion is one level per number, so at most 10 levels plus the first call. That is far below Python's default recursion limit of 1000.

    Complexity

    Time: O(n * 2^n). The search reaches 2^n finished subsets, and saving each one copies up to n numbers. The calls that don't reach the end are fewer than the ones that do, so they add only a constant factor.

    Space: O(n) besides the answer. The extra memory is current, which holds at most n numbers, and one call on the stack per index. The answer itself, with 2^n subsets, is output and isn't counted.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]]: two subsets, without the number and then with it.
    • Negative numbers and order. [3, -1] gives [[], [-1], [3], [3, -1]]. The numbers inside a subset follow nums, not their size, and the subsets follow the skip-before-take rule, not sorted order.
    • The empty subset. It is part of the answer, and it is always the first entry. It comes from skipping every number.
    • Taking before skipping. Swapping the two recursive calls still finds all the subsets, but in a different order, so the lesson's tests would fail.
    • Appending current without copying. This gives a list full of empty lists, as shown above.
    • Forgetting return in the base case. The code would then try nums[i] with i == len(nums) and raise an IndexError.

    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 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] gives a list of 1024 subsets.
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free