LeetCode 78: Subsets Solution in Python Explained

Problem Statement

LeetCode 78, Subsets, is a medium-level problem where you’re given an integer array nums containing distinct elements. Your task is to return all possible subsets (the power set) of the array, in any order. Each subset is a list of integers from nums, and the result must not contain duplicate subsets.

Constraints

1 <= nums.length <= 10: Array length is between 1 and 10.
-10 <= nums[i] <= 10: Elements are within this range.
All elements in nums are distinct.

Example

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Explanation: All 2^3 = 8 subsets of [1,2,3].

Input: nums = [0]
Output: [[],[0]]
Explanation: 2^1 = 2 subsets: empty and [0].

Input: nums = [1,2]
Output: [[],[2],[1],[1,2]]
Explanation: 2^2 = 4 subsets.

Understanding the Problem

How do you solve LeetCode 78: Subsets in Python? For nums = [1,2,3], generate all possible subsets: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]], totaling (2^3 = 8). Each element can either be included or excluded, and since elements are distinct, all subsets are unique. We’ll explore two approaches: a Backtracking Solution (optimal and primary) and an Alternative with Bit Manipulation (clever and concise). The backtracking method runs in O(2^n) time with O(n) space for the recursion stack, where (n) is the array length.

Solution 1: Backtracking Approach (Primary)

Explanation

Use backtracking to build subsets by deciding for each element whether to include it or not. Start with an empty subset, explore all possibilities by adding elements one at a time, and add each valid subset to the result. The process naturally generates all (2^n) subsets without duplicates due to the distinct elements.

Here’s a flow for [1,2,3]:

Start: []
i=0: [] (skip), [1] -> [1] (skip), [1,2] -> [1,2] (skip), [1,2,3]
i=1: [2] -> [2] (skip), [2,3]
i=2: [3]
Result: [[],[3],[2],[2,3],[1],[1,2],[1,3],[1,2,3]]

Initialize Result.

List to store all subsets.

Backtrack.

Build subsets by including/excluding elements.

Add Subsets.

Append current subset at each step.

Return Result.

Step-by-Step Example

Example 1: nums = [1,2,3]

We need [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].

Goal: Generate all subsets of [1,2,3].
Result for Reference: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]].
Start: nums = [1,2,3], result = [], curr = [], start = 0.
Step 1: start = 0.

Add [], result = [[]].
Include 1, curr = [1].

Add [1], result = [[],[1]].
start = 1, include 2, curr = [1,2].

Add [1,2], result = [[],[1],[1,2]].
start = 2, include 3, curr = [1,2,3].

Add [1,2,3], result = [[],[1],[1,2],[1,2,3]].

Backtrack, curr = [1,2].

Backtrack, curr = [1], start = 2, include 3, curr = [1,3].

Add [1,3], result = [[],[1],[1,2],[1,2,3],[1,3]].

Backtrack, curr = [].

Step 2: start = 1.

Include 2, curr = [2].

Add [2], result = [[],[1],[1,2],[1,2,3],[1,3],[2]].
start = 2, include 3, curr = [2,3].

Add [2,3], result = [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3]].

Backtrack, curr = [].

Step 3: start = 2.

Include 3, curr = [3].

Add [3], result = [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]].

Finish: Return [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] (order may vary).

Example 2: nums = [0]

We need [[],[0]].

Start: curr = [], start = 0.
Step 1: Add [], result = [[]].

Include 0, curr = [0], add [0], result = [[],[0]].

Finish: Return [[],[0]].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

def subsets(nums: list[int]) -> list[list[int]]:
    # Line 1: Initialize result
    result = []

    # Line 2: Backtracking helper
    def backtrack(curr: list[int], start: int) -> None:
        # Line 3: Add current subset
        result.append(curr[:])

        # Line 4: Explore numbers from start
        for i in range(start, len(nums)):
            curr.append(nums[i])
            backtrack(curr, i + 1)
            curr.pop()

    # Line 5: Start backtracking
    backtrack([], 0)

    # Line 6: Return all subsets
    return result

Alternative: Bit Manipulation Approach

Explanation

Use bit manipulation to generate all (2^n) subsets by representing each subset as a binary number from 0 to (2^n - 1). Each bit position corresponds to an element in nums: 1 means include, 0 means exclude. Iterate through all possible binary numbers and construct subsets accordingly.

For [1,2,3]:

0: 000 -> []
1: 001 -> [3]
2: 010 -> [2]
3: 011 -> [2,3]
4: 100 -> [1]
5: 101 -> [1,3]
6: 110 -> [1,2]
7: 111 -> [1,2,3]

Generate Binary Numbers.

Range from 0 to \(2^n - 1\).

Build Subsets.

Check each bit to include elements.

Return Result.

Step-by-Step Example (Alternative)

For [1,2,3]:

Start: n = 3, result = [].
Step 1: mask = 0 (000).

[], result = [[]].

Step 2: mask = 1 (001).

[3], result = [[],[3]].

Step 3: mask = 2 (010).

[2], result = [[],[3],[2]].

Step 4: mask = 3 (011).

[2,3], result = [[],[3],[2],[2,3]].

Step 5: mask = 4 (100).

[1], result = [[],[3],[2],[2,3],[1]].

Step 6: mask = 5 (101).

[1,3], result = [[],[3],[2],[2,3],[1],[1,3]].

Step 7: mask = 6 (110).

[1,2], result = [[],[3],[2],[2,3],[1],[1,3],[1,2]].

Step 8: mask = 7 (111).

[1,2,3], result = [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]].

Finish: Return result.

How the Code Works (Bit Manipulation)

def subsetsBit(nums: list[int]) -> list[list[int]]:
    # Line 1: Initialize result
    result = []
    n = len(nums)

    # Line 2: Iterate through all possible binary masks
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):  # Check if bit i is set
                subset.append(nums[i])
        result.append(subset)

    # Line 3: Return all subsets
    return result

Complexity

Backtracking:

Time: O(2^n) – Generate all \(2^n\) subsets.
Space: O(n) – Recursion stack depth.

Bit Manipulation:

Time: O(2^n) – Iterate through \(2^n\) masks.
Space: O(1) – Excluding output space.

Efficiency Notes

Both solutions are O(2^n) time, as they generate all (2^n) subsets, optimal for LeetCode 78. Backtracking uses O(n) space for the stack, while Bit Manipulation uses O(1) extra space (excluding output), making it slightly more space-efficient but less intuitive.

Key Insights

Tips to master LeetCode 78:

Power Set: \(2^n\) subsets from include/exclude choices.
Backtracking: Build incrementally with recursion.
Bitwise: Use binary representation for all combinations.

Additional Example

For nums = [1,2]:

Goal: [[],[2],[1],[1,2]].
Backtracking: [], [2], [1], [1,2], return [[],[2],[1],[1,2]].
Result: [[],[2],[1],[1,2]].

Edge Cases

Single Element: [1] – Return [[],[1]].
Max Length: \(n=10\) – Return \(2^{10} = 1024\) subsets.
Empty Input: Not applicable per constraints.

Final Thoughts

The Backtracking solution is a versatile choice for LeetCode 78 in Python—clear, recursive, and efficient, with Bit Manipulation offering a clever, compact alternative. For a related challenge, try LeetCode 77: Combinations to tweak for fixed sizes! Ready to subset? Solve LeetCode 78 on LeetCode now and test it with [1,2,3] or [0] to master subset generation. Dive in and explore all possibilities!