Subsets (LeetCode 78)

You get an array of distinct integers, nums, and have to return every subset of it, including the empty one and the whole array. Order doesn’t matter, so [1, 2] and [2, 1] are the same subset.

For nums = [1, 2, 3] there are 8:

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

The idea

This is backtracking again, the same add, recurse, undo loop as N-Queens and Combination Sum. And just like Combination Sum, the thing holding it together is index. It’s a parameter of helper, and the loop starts at i = index, not at 0. That’s what stops [1, 2] and [2, 1] from both showing up: once I’ve moved past a number, I never go back for it.

The code

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

    public void helper(List<List<Integer>> result, List<Integer> currSubset, int[] nums, int index) {
        result.add(new ArrayList<>(currSubset));
        for (int i = index; i < nums.length; i++) {
            currSubset.add(nums[i]);
            helper(result, currSubset, nums, i + 1);
            currSubset.remove(currSubset.size() - 1);
        }
    }
}

What’s different this time

Two small changes from Combination Sum, and they’re the whole difference between the problems.

I recurse with i + 1, not i. In Combination Sum I passed i so the same number could be picked again. Here each number can only be in a subset once, so the next call starts one past it.

Every call saves its subset, right away. There’s no target == 0 check. Every partial list I build along the way is already a valid subset, so helper adds a copy of currSubset the moment it’s called. There’s no explicit base case either: when index reaches nums.length, the loop just doesn’t run, and the call returns on its own.

Here’s the actual order the subsets come out in for [1, 2, 3]:

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

You can see the backtracking in it. It goes as deep as it can with 1 first, [1], then [1, 2], then [1, 2, 3]. Then it backs up, drops the 2, and tries [1, 3]. Only after every subset starting with 1 is done does it move on to 2, and because of index, nothing after that ever goes back and picks up the 1.

Runtime

There are $2^n$ subsets, since each number is either in or out, and helper gets called exactly once per subset. Copying a subset into result takes up to $O(n)$, so the whole thing is $O(n \cdot 2^n)$. The recursion goes at most $n$ calls deep, so the extra space is $O(n)$, not counting the subsets I return.