Subsets

LeetCode 78 | Difficulty: Medium

Medium

Problem Description

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

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 10

• -10 <= nums[i] <= 10

• All the numbers of nums are unique.

Topics: Array, Backtracking, Bit Manipulation

---

Approach

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: Iterative (Cascading)

Start with [[]] and, for each number in nums, append it to every existing subset to create new subsets.

Iterative

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>> { new List<int>() };
        foreach (int n in nums) {
            int size = result.Count;
            for (int i = 0; i < size; i++) {
                var next = new List<int>(result[i]) { n };
                result.Add(next);
            }
        }
        return result;
    }
}

Solution 2: Backtracking

Build subsets by choosing/skipping each element.

Backtracking

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>>();
        Backtrack(nums, 0, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] nums, int start, List<int> current, IList<IList<int>> result) {
        result.Add(new List<int>(current));
        for (int i = start; i < nums.Length; i++) {
            current.Add(nums[i]);
            Backtrack(nums, i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

Solution 3: Bit Manipulation

Each subset corresponds to an n-bit mask (0 to 2^n - 1).

Bitmask

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        int n = nums.Length;
        var result = new List<IList<int>>();
        for (int mask = 0; mask < (1 << n); mask++) {
            var subset = new List<int>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) subset.Add(nums[i]);
            }
            result.Add(subset);
        }
        return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Iterative / Backtracking / Bitmask	$O(n \cdot 2^n)$	$O(n \cdot 2^n)$ output

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Identify pruning conditions early to avoid exploring invalid branches.