I. Bitmask Enumeration

Core Idea

For a set of n elements, each element has two choices: either be included in or excluded from a subset. Therefore, there are exactly 2^n possible subsets.

We can represent each subset using a bitmask: a binary number of length n where each bit indicates whether the corresponding element is included (1) or not (0).

• e.g.

    nums = [1,2,3,4,5,6,7]
  

  A possible subset {2, 4, 7} can be encoded as:

  
    nums =  [1, 2, 3, 4, 5, 6, 7]
    mask =   0  1  0  1  0  0  1 
    → binary: 0101001
  

  Each 1 in the mask represents the inclusion of the corresponding element in the subset.

Algorithm Logic

We reverse the above perspective: instead of choosing elements to build a subset, we iterate through all integers from 0 to 2^n - 1, treating each integer as a bitmask.

For each bit j in the binary representation of the current integer i, if the j-th bit is 1, we include nums[j] in the current subset. For example, if the bit at position 1 (counting from the right, 0-indexed) is 1, it corresponds to nums[1], which is 2.

This approach allows us to systematically and efficiently enumerate all possible subsets without recursion, using simple bitwise operations.

Implementation Note

Quick Recap of Bitwise Operations

• (i >> j)
  • Performs a right bit shift, moving the binary representation of integer i to the right by j positions.
  • Equivalent to: i >> j ≈ floor(i / 2^j)
  • e.g.

    
    int i = 6;       // binary: 110
    int j = 1;
    int result = i >> j;  // 110 >> 1 = 011 = 3
    

• (i >> j) & 1
  • Checks whether the j-th bit (from the right, 0-indexed) of integer i equals 1.
    • i >> j: shifts the target bit to the least significant position.
    • & 1: masks all other bits, leaving only the last bit (0 or 1).
    • e.g.

      int i = 6; // binary: 110
      (i >> 1) = 011 → & 1 = 1   → Bit at position 1 is 1
      (i >> 2) = 001 → & 1 = 1   → Bit at position 2 is 1
      (i >> 0) = 110 → & 1 = 0   → Bit at position 0 is 0
      

• 1 << n
  • Performs a left bit shift, moving the binary representation of 1 to the left by n positions. It computes the value of 2 to the power of n. Mathematically, 1 « n is equivalent to 2^n.
  • e.g.

    1 << 3 
    → binary: 1000 → decimal: 8 (which is 2^3)
    

Solution

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

        // Iterate through all bitmasks from 0 to 2^n - 1
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();

            // For each bit position j, check if the j-th bit is set to 1
            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) == 1) {
                    subset.add(nums[j]);
                }
            }

            res.add(subset);
        }

        return res;
    }
}

Time Complexity: O(N·2^N)
    - The outer loop runs from 0 to 2^n - 1, so it executes 2^n times.
    - Inside the loop, for each bitmask of length n, we check all n bits (from 0 to n - 1).
Space Complexity: O(N·2^N)
    - The result list stores all 2^N subsets.
    - Each subset can contain up to N elements.

II. BFS List-Based Approach

Core Idea

We can draw a parallel between Leetcode 78 – Subsets and Leetcode 17 – Letter Combinations of a Phone Number, where both problems can be approached as a form of Breadth-First Search (BFS) traversal.

In both problems, the idea is to incrementally build combinations or subsets as new elements (either digits or numbers) are processed. The underlying mechanics are similar — we start with an initial state and expand the result level by level.

• e.g. nums = [7, 8, 9]

    Step 0: Initialization: 
            Start with the empty subset: 
        List: [ [] ]
  
    Step 1: (i = 0) Process number 7
            Add '7' to each existing subset (currently only [])
        Updated List: [ [], [7] ]
  
    Step 2: (i = 1) Process number 8
            Add '8' to each existing subset: [], [7]
            - Add 8 to []  → [8]
            - Add 8 to [7] → [7, 8]
  
        Updated List: [ [], [7], [8], [7,8] ]
  
    Step 3: (i = 2) Process number 9
            Add '8' to each existing subset: [], [7], [8], [7,8]
            - Add 9 to []    → [9]
            - Add 9 to [7]   → [7, 9]
            - Add 9 to [8]   → [8, 9]
            - Add 9 to [7,8] → [7, 8, 9]
          
        Final List: [ [], [7], [8], [7,8], [9], [7, 9], [8, 9], [7, 8 , 9] ]
  

Implementation Note

In Leetcode 17, we used a queue to perform a BFS traversal. Each level corresponds to adding one digit to existing combinations. Importantly:

• Intermediate combinations are temporary — we dequeue them, extend them with the current digit, and then enqueue the new combinations.
• Only the final combinations are retained.

In contrast, for Leetcode 78, we must retain all intermediate results because every subset generated during the process is part of the final answer. Therefore:

• We do not use a queue or perform dequeue operations.
• Instead, we use a List<List<Integer>> that we iterate and expand, appending new subsets at each step.

📌 Algorithm

• (1) Initialize the result list:
  • Start with a list containining the empty subset [ [] ].
• (2) Iterate through each number num in nums:
  • For each existing subset in the list, create a new subset by adding num .
  • Add all these new subsets into the result list.

Solution

class Solution{
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>()); // Start with the empty subset

        for (int num : nums) {
            int size = res.size();

            for (int i = 0; i < size; i++) {
                List<Integer> subset = new ArrayList<>(res.get(i));
                subset.add(num);
                res.add(subset);
            }
        }

        return res;
    }
}

Time Complexity: O(N·2^N)
For each number, we copy each subset of size up to n costs O(2^N) and add an element in O(N)

Space Complexity: O(N·2^N)
We are storing 2^N subsets. Each subset is an ArrayList<Integer> of size up to N.

III. DFS Recursive Backtracking

Core Idea

We can model the solution as a decision tree traversal:

• Each level represents processing the i-th element in the array.
• Each node corresponds to a valid subset (the current decision path).
• Each branch represents a decision to include an element.

Solution

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

    public void backtrack(List<Integer> currentPath, int[] nums, int start, List<List<Integer>> res) {
        // Every path is a valid subset
        res.add(new ArrayList<>(currentPath)); 

        for (int i = start; i < nums.length; i++) { 
            currentPath.add(nums[i]);                   // Make a decision
            backtrack(currentPath, nums, i + 1, res);   // Explore next level
            currentPath.remove(currentPath.size() - 1); // Backtrack
        }
    }
}