Skip to main content

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​

Complexity Analysis​

ApproachTimeSpace
Backtracking$O(n! or 2^n)$$O(n)$
Bit Manipulation$O(n) or O(1)$$O(1)$

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.