{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Subsets – Solution & Complexity

Interview solutions
/
Subsets

Solution Walkthrough

  1. Step 1: Understand the Goal

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

  2. Step 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. Step 3: Build the Algorithm

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

  4. Step 4: Check Edge Cases

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

  5. Step 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)Combination Sum II solution (medium)Generate Parentheses solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?