{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Subsets – Solution & Complexity

Interview solutions
/
Subsets

1. Understand the Goal

  • Identify the required output and the state that changes.
  • Use the examples to rule out tempting but incorrect interpretations.

2. Choose the Core Pattern

  • This problem is best exposed by Backtracking makes an include/exclude decision for each value.
  • Maintain only the state needed for the next operation.

3. Build the Algorithm

  • Process each state once when possible.
  • Record state before scheduling dependent work to avoid duplicates.

4. Check Edge Cases

  • Verify the smallest input, impossible cases, and repeated values where allowed.
  • Keep output ordering deterministic.

5. Final Solution and Complexity

  • Time complexity is O(n*2^n).
  • Space complexity is O(n*2^n).
def subsets(nums: list[int]) -> list[list[int]]:
    answer, current = [], []
    def backtrack(index):
        if index == len(nums):
            answer.append(current.copy()); return
        current.append(nums[index]); backtrack(index + 1); current.pop()
        backtrack(index + 1)
    backtrack(0)
    return answer

FAQ

See also

Practice Subsets online (run code in the browser)Combination Sum solution (medium)Permutations solution (medium)Single Number solution (easy)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?