Developers

Subsets

MediumBacktrackingGrade CAlso known as LeetCode 78

Given a list nums of distinct integers, return all of its subsets (the power set). A subset may have any number of elements, from none to all of them, and the empty subset and the whole list both count.

Do not return the same subset twice. The subsets can be returned in any order, and the numbers inside one subset can be in any order.

Examples

Input nums = [1, 2, 3]
Output [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Input nums = [0]
Output [[], [0]]
Input nums = [4, 5]
Output [[], [4], [5], [4, 5]]

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • all the numbers in nums are different

Stuck? Take one hint at a time

Common mistakes
  • Appending current itself to the result instead of a copy, so every entry ends up as the same list, empty at the end.
  • Forgetting to undo the last choice after the recursive call, so choices pile up.
  • Starting the loop at 0 in every call, which produces [1, 2] and [2, 1] as different subsets.
  • Recording only when current reaches full length, which finds just one subset.
  • Modifying result while iterating over it in the doubling method. Take the size first, or build the copies first and add them afterwards.
Questions an interviewer may ask next
  • The list may contain duplicates, and no subset may repeat. (Sort first and skip a number equal to the one before it at the same level. This is Subsets II.)
  • Return only the subsets that add up to a target. (Combination Sum style: prune when the sum is too large.)
  • Return only subsets of size k. (Combinations: stop at length k, and stop early when too few numbers remain.)
  • Generate the subsets with a bitmask from 0 to 2^n - 1. How does bit i decide whether nums[i] is in?

How often this is reported

Commonly reported across 6 of 25 tracked companies
6/25

Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.