Subsets

Generate all possible subsets (the power set) of a list of distinct integers.

recursion backtracking subsets

Implement the function `subsets(nums)` that takes a list of distinct integers and returns a list of all possible subsets (the power set). The order of the subsets themselves does not matter, but within each subset, the elements must appear in the same relative order as in the original `nums` list. The output must contain no duplicate subsets; it must contain exactly 2^n subsets where n = len(nums). For example, if `nums = [1, 2, 3]`, the output could be `[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]` or any permutation of those subsets. You may implement the function using recursion, backtracking, or any iterative approach.

Constraints

- `0 <= len(nums) <= 10`
- Elements of `nums` are distinct integers.
- The output must contain exactly 2^n subsets, where n is the length of `nums`.
- The total number of subsets is at most 1024, so efficiency is not critical.

Example

>>> subsets([])
[[]]
>>> subsets([1])
[[], [1]]
>>> subsets([1, 2])
[[], [1], [2], [1, 2]]

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think recursively: the subsets of a list can be formed by taking each subset of the rest and either including or excluding the first element.

Use a backtracking helper that builds subsets incrementally, adding the current subset to the result at every step.

Ensure that the elements in each subset maintain the original order by iterating through the list with an index.

The base case is when the index reaches the end of the list, or you can start with an empty list and extend it.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.