FunctionRacerProblemsRace

Subsets by Doubling

EasyRecursionPython, JavaScript, TypeScript, Java, C++

nums is a list of distinct integers. Build the list of all of its subsets by this procedure: start with a list that holds only the empty subset []. Then take the elements of nums from left to right; for each element, copy every subset collected so far, append the element to the end of each copy, and add the copies after the subsets already collected, keeping their order. Return the final list of subsets, in exactly that order.

An iterative version of the procedure works, but the recursive one is just as short: the answer for nums is the answer for nums without its last element, followed by those same subsets with the last element appended to each.

For example, [1, 2] gives [[], [1], [2], [1, 2]], and [] gives [[]].

Example 1

nums [1,2]
returns [[],[1],[2],[1,2]]

Start with [[]]. The element 1 adds [1], giving [[], [1]]. The element 2 adds [2] and [1, 2] after them.

Example 2

nums []
returns [[]]

There is nothing to add, so only the empty subset remains.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems