78. Subsets - Detailed Explanation

Problem Statement

Description:
Given an array of distinct integers nums, return all possible subsets (the power set).

A subset is a collection of elements from nums (possibly none), and each subset must be unique.

Example 1:

• Input: nums = [1, 2, 3]
• Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
• Explanation:
  • The empty set [] is a subset.
  • All one-element subsets: [1], [2], [3]
  • All two-element subsets: [1, 2], [1, 3], [2, 3]
  • The full set: [1, 2, 3]

Example 2:

• Input: nums = [0]
• Output: [[], [0]]
• Explanation:
  • The empty set and the single-element set [0] are all possible subsets.

Constraints:

• The length of nums is between 1 and 10 (or more depending on variations).
• All elements in nums are distinct.
• The solution should generate 2ⁿ subsets (where n is the number of elements), so be mindful of exponential growth in output.

Hints

• Hint 1:
  Think of each element as having two options: either you include it in a subset or you do not. This binary decision for every element suggests that the total number of subsets will be 2ⁿ.

• Hint 2:
  Consider using recursion (backtracking) where at each step you decide to include or exclude the current element, then move on to the next element.

• Hint 3:
  You can also use iterative approaches or bit manipulation to generate all possible combinations.

Approach 1: Backtracking (Depth-First Search)

Idea

Use recursion to explore two choices at every index: include the current element or skip it. This way, you build a tree where each node represents a decision point, and the leaves of this tree represent one subset.

Steps

1. Start with an empty subset:
   Begin with an empty list representing the current subset.

2. Recursive Decision:
   For each element in the array, decide:

   • Include the element in the current subset.
   • Exclude the element and move to the next.

3. Base Case:
   When you reach the end of the array, add the current subset to your list of subsets.

4. Backtrack:
   Remove the last element (if added) and try the next decision.

Visual Walkthrough

For nums = [1, 2, 3]:

• Start with [].
• At index 0 (element 1):
  • Include 1 → [1]
    • At index 1 (element 2):
      • Include 2 → [1, 2]
        • At index 2 (element 3):
          • Include 3 → [1, 2, 3] → add to result.
          • Exclude 3 → [1, 2] → add to result.
      • Exclude 2 → [1]
        • At index 2 (element 3):
          • Include 3 → [1, 3] → add to result.
          • Exclude 3 → [1] → add to result.
  • Exclude 1 → []
    • At index 1 (element 2):
      • Include 2 → [2]
        • At index 2 (element 3):
          • Include 3 → [2, 3] → add to result.
          • Exclude 3 → [2] → add to result.
      • Exclude 2 → []
        • At index 2 (element 3):
          • Include 3 → [3] → add to result.
          • Exclude 3 → [] → add to result.

Approach 2: Iterative Method

Idea

Start with an empty subset and then for each element in nums, add it to every existing subset in your results list to create new subsets.

Steps

1. Initialize Result:
   Start with result = [[]].

2. Iterate Through nums:
   For each number, iterate over the current subsets in result and add a new subset that includes the current number.

3. Combine:
   Append these new subsets back to the result.

Visual Walkthrough

For nums = [1, 2, 3]:

• Start: [[]]
• Process 1: Add [1] to each subset → [[], [1]]
• Process 2: For each subset in [[], [1]]:
  • Add 2 → [2] and [1, 2] → now result becomes [[], [1], [2], [1, 2]]
• Process 3: For each subset in [[], [1], [2], [1, 2]]:
  • Add 3 → [3], [1, 3], [2, 3], [1, 2, 3] → final result becomes [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].

Code Implementation

Python Code (Backtracking Approach)