Start learning free

LESSON 351 OF 536 · BACKTRACKING

Subsets in JavaScript: Backtracking with Skip and Take Choices

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

Given an array 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

    JAVASCRIPT · BACKTRACKING

    Subsets in JavaScript, explained

    Problem overview

    The method subsets(nums) receives an array of distinct integers and returns every subset of it: every way to pick some of its numbers, from none (the empty subset) up to all of them. The result is an array of arrays.

    The numbers of each subset keep their order from nums, and the subsets themselves come in a fixed order, the one 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 first, then the ones with it, and so on. The empty subset is always first and the whole array 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. In [[],[0]], the answer for [0], there are two subsets: without the number, then with it. For [3, -1] the result is [[],[-1],[3],[3,-1]]: the last subset is written [3,-1], in the order of nums, not sorted.

    Approach: skip or take, one number at a time

    Each number is either in a subset or not, so a subset is a string of n yes-or-no choices, and there are 2^n subsets. Backtracking walks through all the choices with one recursive function.

    The function works on one index i of nums at a time and keeps the numbers taken so far in a list current. At index i it makes two choices, in this order:

    1. Skip nums[i]: go on to index i + 1 with current as it is.
    2. Take nums[i]: add it to current, go on to index i + 1, then remove it again.

    When i reaches the end of nums, every number has been skipped or taken, and current is one complete subset: save a copy of it. Removing the number after the take branch is the "back" in backtracking. It restores current to what the caller handed in, so the caller can go on as if nothing happened.

    Trying skip before take gives exactly the required order. All the subsets without nums[0] are produced before the first one with it, and the same holds at every level. Here are the first events of the search for [1, 2, 3]:

    i=0 skip 1
i=1 skip 2
i=2 skip 3
save []
i=2 take 3 [3]
save [3]
i=1 take 2 [2]
i=2 skip 3
save [2]
i=2 take 3 [2,3]
save [2,3]
i=0 take 1 [1]

    The first subset saved is the empty one, then [3], [2] and [2,3], and after that the search takes 1 and produces the other four.

    Step by step

    1. Create result as a constant empty array. It collects the subsets.
    2. Start the search with this.backtrack(nums, 0, [], result): index 0 is the first number to decide about, and the subset being built is empty.
    3. Return result. The helper added to this same array.
    4. Declare the helper backtrack(nums, i, current, result) inside the class. Each call decides about nums[i] and calls itself for the next index.
    5. Check whether i has reached the end: i === nums.length.
    6. Save a copy and return. [...current] copies the numbers into a new array. current keeps changing, so the result needs a snapshot.
    7. Skip first: call this.backtrack(nums, i + 1, current, result) without touching current. This finds every subset that doesn't contain nums[i].
    8. Take: push nums[i] onto the end of current. Numbers are added in index order, so each subset keeps the order of nums.
    9. Recurse again with the same arguments. This time current holds nums[i], so this call finds every subset that contains it. Together with the skip call, each subset is found exactly once.
    10. Undo the choice with current.pop(), which removes the last number.

    The solution in JavaScript

    class Solution {
    subsets(nums) {
        const result = [];
        this.backtrack(nums, 0, [], result);
        return result;
    }
    backtrack(nums, i, current, result) {
        if (i === nums.length) {
            result.push([...current]);
            return;
        }
        this.backtrack(nums, i + 1, current, result);
        current.push(nums[i]);
        this.backtrack(nums, i + 1, current, result);
        current.pop();
    }
}

    The JavaScript details worth a closer look:

    • The copy matters. Arrays are passed by reference, so every call works on the same current. If the code pushed current itself, result would hold several references to one array, and at the end that array is empty again. A version without the copy returns [[],[],[],[]] for [7, 8], instead of [[],[8],[7],[7,8]].
    • [...current] is the spread syntax: it builds a new array with the same elements. It is a shallow copy, which is enough because the elements are numbers.
    • const for result. const stops the variable from being reassigned, but the array it names can still grow. That is why result.push(...) works on a constant.
    • Methods are called through this. backtrack belongs to the class, so the calls are this.backtrack(...). Without this., JavaScript looks for a variable named backtrack and throws a ReferenceError.
    • === for the index check. Both sides are numbers, and === compares them without converting types.

    Complexity

    Time: O(n · 2^n). There are 2^n subsets, and copying one takes up to n steps. The recursion makes about 2^(n+1) calls in total, which is within the same bound.

    Space: O(n) beyond the answer. The extra memory is current, which holds at most n numbers, and the recursion, which is n + 1 calls deep. The answer itself holds up to n · 2^n numbers. With n up to 10, that is at most 1,024 subsets.

    Edge cases and common mistakes

    • One number. [0] returns [[],[0]]: the skip branch saves the empty subset, and the take branch saves [0].
    • Two numbers. [5, 6] returns [[],[6],[5],[5,6]].
    • Negative numbers and order. [3, -1] returns [[],[-1],[3],[3,-1]]. The code never sorts or compares values, so the subsets follow the order of nums.
    • The count. For n numbers the result holds 2^n subsets, including the empty one. For ten numbers that is 1,024.
    • Forgetting the copy. The result then holds the same array several times, which is empty at the end.
    • Forgetting pop(). current keeps numbers that should have been removed, so later subsets contain numbers they shouldn't.
    • Taking before skipping. The subsets are all there, but in a different order, and the lesson's tests expect skip-first order.
    • Saving at every call. Only the calls at i === nums.length save. Saving earlier would store the same subset many times.

    Testing

    • [1, 2, 3] gives [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]].
    • [0] gives [[],[0]].
    • [3, -1] gives [[],[-1],[3],[3,-1]].
    • [5, 6] gives [[],[6],[5],[5,6]].
    • [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] returns 1,024 subsets.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free