Subsets

78. Subsets – LeetCode

Problem Statement

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

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

Examples

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

Constraints

Intuition

Every element has two choices: include it or exclude it.
So for n elements, total subsets = 2ⁿ.

This matches the number of binary numbers from 0 to 2ⁿ - 1.
We can map each bit in a binary number to an element in the array:

This technique is called bitmasking.

Approach: Bitmasking

  1. For each number i from 0 to 2ⁿ - 1 (inclusive), treat it as a bitmask.

  2. For each bit j in i:

    • If the bit is set → include nums[j] in the current subset

  3. Add the generated subset to the result list.

Java Code

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < (1 << n); i++) {
            List<Integer> in = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    in.add(nums[j]);
                }
            }
            ans.add(in);
        }

        return ans;
    }
}

Time and Space Complexity

Metric Value
Time Complexity O(n × 2ⁿ)
Space Complexity O(n × 2ⁿ)
Explanation 2ⁿ subsets, each of size up to n

Dry Run

Input: nums = [1, 2]

  1. i = 0 → 00 → []

  2. i = 1 → 01 → [1]

  3. i = 2 → 10 → [2]

  4. i = 3 → 11 → [1, 2]

Output: [[], [1], [2], [1, 2]]

Conclusion

This problem is a classic illustration of using bitmasking to generate all combinations: