78. Subsets

📝 Problem Details

• Title: 78. Subsets
• Link: https://leetcode.com/problems/subsets/
• Difficulty: Medium
• Tags/Categories: Backtracking

---

• given an inter array nums
• each elements in nums is unique
• return all possible subsets (the power set)
• solution set must not contain duplicate subsets
• can be returned in any order

💭What Were My Initial Thoughts?

- this is an enumeration problem , meaning we are listing out all possible valid solutions --> strong indicator for backtracking 

Validity of a backtracking approach?
- decision?
	- at each step we can either include or exclude an element from the array in our subset
- what is an invalid solution?
	- a choice might lead to a redundant computation

- why use backtracking over greedy or dp?
	- we need to explore all possible solutions so a greedy algo wont work 
	- we dont build an optimal solution from smaller optimal solutions 
	- the constraint that subsets must be **unique** suggests that some kind of pruning (avoiding redundant solutions) could help with efficiency.

💡 Explanation of Solution

Base case: every recursive call stores the current subset in result

Recursive exploration: 
	- iterate through the elements starting from `index`
	- add the current element to the subset
	- recursively call dfs with the next index (i+1)
	- backtrack by removing the lat element (undo the choice)

Pruning optimization:
	- we ensure each number is considerd only once by using i+1 as the next index
	- no need to check for duplicates only contains distinct integers

⌛ Complexity Analysis

Time Complexity: O(n * 2^n)
- the number of subsets for n elements is 2^n
- each subset takes O(n) time to construct
- large but optimal for enumeration problems 

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        dfs(nums, 0, current, result);
        return result;
    }
 
    void dfs(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
        // add the current subset to the result
        result.push_back(current);
 
        // explore further by including each remaining element
        for(int i = index; i < nums.size(); i++) {
            // choose
            current.push_back(nums[i]);
 
            // explore
            dfs(nums, i + 1, current, result);
 
            // backtack (undo the choice)
            current.pop_back();
        }
    }
};