LeetCode Problem 78 - Subsets

 Problem Statement

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets.

Example 1:

Input: nums = [1,2,3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Example 2:

Input: nums = [0]
Output: [[], [0]]

Optimal Approach: Backtracking

The best way to generate all subsets is Backtracking, which explores all possible combinations recursively. The algorithm uses DFS (Depth-First Search) and maintains a temporary list for building subsets.

Key Idea

1. Start with an empty subset [].
2. Recursively add each element and explore further subsets.
3. After exploring, backtrack (remove last element) to explore other possibilities.

LeetCode-Compatible C++ Solution

class Solution {
public:
    void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& subset, int index) {
        res.push_back(subset);
        for (int i = index; i < nums.size(); i++) {
            subset.push_back(nums[i]);
            backtrack(nums, res, subset, i + 1);
            subset.pop_back();
        }
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> subset;
        backtrack(nums, res, subset, 0);
        return res;
    }
};

Step-by-Step Explanation

1. We use res to store all subsets and subset as a temporary list.
2. Base Case: Each recursive call adds subset to res.
3. Recursive Case:
   • Iterate through nums.
   • Add nums[i] to subset.
   • Recursively call backtrack() with the next index.
   • Remove the last element to backtrack.

Dry Run

For nums = [1,2,3]:

Start: []
Add 1 → [1]
  Add 2 → [1,2]
    Add 3 → [1,2,3] (store & backtrack)
  Remove 3 → [1,2]
Remove 2 → [1]
  Add 3 → [1,3] (store & backtrack)
Remove 1 → []
  Add 2 → [2]
    Add 3 → [2,3] (store & backtrack)
  Remove 3 → [2]
Remove 2 → []
  Add 3 → [3] (store & backtrack)

Final Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Generate all subsets)	O(2^N * N)	O(2^N)	Inefficient for large N
Iterative Bit Masking (Use bits to represent subsets)	O(2^N * N)	O(2^N)	Less intuitive than recursion
Sorting + Two Pointers	N/A	N/A	Not applicable

Best Solution & Why?

The Backtracking approach (DFS) is the best because:

• Efficient: It avoids unnecessary calculations.
• Scalable: Works well for large inputs.
• Easy to understand: Clearly follows subset generation rules.

Complexity Analysis

• Time Complexity: O(2^N * N) (Each element has 2 choices: include or exclude, multiplied by the N iterations for copying results.)
• Space Complexity: O(2^N) (Result storage in res.)

Conclusion

The best way to generate all subsets of a given array is Backtracking, as it efficiently explores all possibilities without redundancy.

Similar Problems for Practice

• Combination Sum
• Permutations
• Letter Combinations of a Phone Number