mafeshsho8lmafeshsho8l
Get Started
All coding questions

Subsets

medium
NeetCode 150backtrackingarrays

Problem

Given a list of distinct integers, return all possible subsets, including the empty set and the full set. The collection of subsets is the power set and may be returned in any order.

Examples

Input: nums = [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
All eight subsets of a three-element set.

Constraints

  • • 1 <= nums.length <= 10
  • • All values are distinct
Hints(tap to reveal)
  • 1. Each element is either in or out of a subset.
  • 2. Backtrack by choosing to include or skip each index.
Optimal approach(spoiler)
  1. Recurse over the array index, building a current subset.
  2. At each index branch into including the element and excluding it.
  3. Record the current subset at the base case when the index passes the end.
  4. Undo the inclusion when backtracking.
  5. There are 2^n subsets, so O(n * 2^n) time.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor