LeetCode 78. Subsets

Posted on In , Views:

🧩 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.

💬 Example

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

💡 Approach: Backtracking

We explore each element’s choice: include or exclude.
Alternatively, we can also use bitmask enumeration.

🔢 Java Code (Backtracking)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

⏱ Complexity Analysis

  • Time: O(n × 2^n) → there are 2^n subsets, each takes up to O(n) to copy
  • Space: O(n) recursion depth (excluding output storage)

✍️ Summary

  • Generates the power set of nums.
  • Backtracking and bitmasking are both standard approaches.
  • Useful in combinatorial problems.

Related problems:

  • lc-90 — Subsets II (with duplicates)
  • lc-46 — Permutations
  • lc-39 — Combination Sum
  • lc-40 — Combination Sum II