Start learning free

LESSON 351 OF 536 · BACKTRACKING

Subsets in Java: Backtracking with Skip and Take

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

    JAVA · BACKTRACKING

    Subsets in Java, explained

    Problem overview

    The method subsets receives an int[] called 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 is written in the order its numbers have in nums.

    The order of the subsets matters too. The lesson decides about the numbers one at a time and always tries skipping before taking. Every subset without nums[0] comes before every subset with it, and inside each group the same rule applies to nums[1], then nums[2], and so on. 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 [0] the result is [[], [0]]. For [3, -1] it is [[], [-1], [3], [3, -1]]: the last subset keeps the order of nums and is not sorted.

    Approach: one choice per number

    Each number has two possible fates: it is skipped or it is taken. With n numbers that is 2 to the power n combinations, and each combination is one subset. That is also the number of results, so any solution does at least that much work.

    The method that generates them is backtracking. Walk through nums by index and keep the numbers taken so far in a list called current. At index i:

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

    When the index reaches the end of nums, every number has been decided, and current is a finished subset. Trying skip before take produces exactly the order the statement asks for. It is the same order as counting in binary: a subset is a string of n bits, 0 for skip and 1 for take.

    The removal in step 2 is what makes the idea work. One list is shared by all the calls. After the "take" branch returns, the number is removed, so the caller sees current exactly as it was before the call and can go on from there. Undoing a choice is the "back" in backtracking.

    Step by step

    1. Create result as a List<List<Integer>> holding a new ArrayList<>(). Each subset is a list of numbers, so the result is a list of lists.
    2. Start the search with backtrack(nums, 0, new ArrayList<>(), result): index 0, nothing taken yet. The helper adds to result every subset that extends the one it receives.
    3. Return result. The helper filled this same list.
    4. Write the helper. backtrack returns void and takes nums, the index i to decide about now, the list current and result.
    5. Stop when i == nums.length. Every number has been skipped or taken.
    6. Save a copy. Inside that if, add new ArrayList<>(current) to result and return. A copy is needed because current keeps changing as the search goes on.
    7. Skip first. Call 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. Numbers are added in index order, so every subset keeps the order of nums.
    9. Recurse again with the same arguments, i + 1 included. This time current holds nums[i], so this call finds every subset that contains it.
    10. Undo. Remove the last number with current.remove(current.size() - 1).

    The solution in Java

    class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    void backtrack(int[] nums, int i, List<Integer> current, List<List<Integer>> result) {
        if (i == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        backtrack(nums, i + 1, current, result);
        current.add(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

    Java details worth a closer look:

    • Copy before saving. result.add(current) would store a reference to the one shared list, and later changes would show in every saved entry. In the end each entry would be the same list, empty after the final undo. Written that way, the call on [1, 2, 3] returns [[], [], [], [], [], [], [], []]: eight entries, all empty. new ArrayList<>(current) copies the numbers into a new list.
    • remove(int) versus remove(Object). On a List<Integer>, an argument of type int removes the element at that index, as in current.remove(current.size() - 1). To remove a value you would write remove(Integer.valueOf(7)). With [5, 1, 7], remove(1) leaves [5, 7], because it removed the element at index 1, not the number 1.
    • Autoboxing. current.add(nums[i]) turns the int into an Integer automatically.
    • The diamond. new ArrayList<>() lets the compiler infer the element type from the declared type.

    Complexity

    Time: O(n * 2^n). There are 2^n subsets, and copying one takes up to n steps. The recursion makes about twice as many calls as there are subsets, which doesn't change the total.

    Space: O(n) besides the answer. The helper holds current, which has at most n numbers, and one call per index, so the recursion is at most n calls deep.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]]: two subsets, without it and then with it.
    • The empty subset is always there, and always first. The skip branch is followed all the way down before anything is taken.
    • The size. With 10 numbers, the largest input allowed, the method returns 1024 subsets.
    • Saving current without copying. It gives lists of empty subsets, as shown above.
    • Forgetting the undo. The taken number stays in current for the rest of the search, and later subsets contain numbers that were never chosen for them.
    • Taking before skipping. The subsets are all there, but in a different order than the tests expect.

    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]].
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free