09.SubsetSum.md

🧩 LeetCode 78 — Subsets

Difficulty: Medium Topic: Backtracking / Recursion / Power Set Language: C++

🧠 Problem Statement

You are given an integer array nums of unique elements. Your task is to return all possible subsets (the power set) of the array.

• The solution must not contain duplicate subsets.
• The order of subsets does not matter.

📥 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] ]

💡 Intuition

Every element in the array has two choices:

1. Include it in the subset ✅
2. Exclude it ❌

If the array has n elements, there are 2^n total subsets. We can use recursion/backtracking to explore all combinations systematically.

🪜 Brute Force Approach

• Use binary representation from 0 to 2^n - 1.
• Each bit represents whether an element is included or not.
• Example: for [1,2,3], binary 101 → subset [1,3].

But, this approach, while correct, is less intuitive and harder to extend when problems become more complex (e.g., with duplicates).

⚡ Optimal Approach — Backtracking

We recursively build subsets by making a choice at each step: include or exclude the current element.

🔹 Algorithm Steps

1. Start from index 0 and an empty subset (ds).

2. At each index:

   • Include the element → Recurse with ind + 1.
   • Exclude the element → Recurse with ind + 1.

3. When we reach the end (ind == nums.size()), we add the current subset to the result.

4. Backtrack (remove the last element added) before exploring the next option.

🧩 Code Implementation

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subset;
        vector<int> ds;
        printSubset(0, ds, subset, nums);
        return subset;
    }

    void printSubset(int ind, vector<int> &ds, vector<vector<int>> &res, vector<int> nums) {
        if (ind == nums.size()) {
            res.push_back(ds);
            return;
        }

        // Include current element
        ds.push_back(nums[ind]);
        printSubset(ind + 1, ds, res, nums);

        // Exclude current element
        ds.pop_back();
        printSubset(ind + 1, ds, res, nums);
    }
};

🔍 Dry Run Example

Let’s take nums = [1,2]

Step	ind	Current Subset (ds)	Action
1	0	[]	Start
2	0	[1]	Include 1
3	1	[1,2]	Include 2
4	2	[1,2]	Add to result
5	1	[1]	Exclude 2
6	2	[1]	Add to result
7	0	[]	Exclude 1
8	1	[2]	Include 2
9	2	[2]	Add to result
10	1	[]	Exclude 2
11	2	[]	Add to result

Result: [ [1,2], [1], [2], [] ]

⏱️ Complexity Analysis

Type	Complexity
Time Complexity	O(2^n * n) — each subset built in O(n) and there are 2^n subsets
Space Complexity	O(n) recursion stack + result storage

💬 Tips & Tricks

• Each recursive path represents one subset.
• Backtracking ensures that after exploring one branch (include), we return to try the other (exclude).
• Order doesn’t matter, but if you want lexicographical order, sort nums first.

🔄 Variations

1. Subsets II (with duplicates) → Need to sort and skip duplicates.
2. Combination Sum / Combination Sum II → Same recursion style but with sum constraints.
3. Permutations → Instead of choosing/excluding, rearrange elements.

❓ FAQs

Q1: Why do we pass nums by value and not by reference? → Here, it doesn’t affect results since we aren’t modifying nums. But for efficiency, you can pass it as const vector<int>& nums.

Q2: Why backtrack (ds.pop_back()) after recursion? → To undo the “include” choice before exploring “exclude”.

Q3: Can this be done iteratively? → Yes! For each number, add it to all existing subsets in the result. Example:

for (int num : nums) {
    int size = res.size();
    for (int i = 0; i < size; i++) {
        auto temp = res[i];
        temp.push_back(num);
        res.push_back(temp);
    }
}