1. Introduction

The Subsets pattern is a fundamental backtracking/DFS-based pattern used to generate all possible subsets (also called the power set) of a given set or array.

Definition:

A subset is any selection of elements from the original set, including the empty set and the set itself.

For example:

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

This pattern is widely used in problems involving:

• Combinatorics
• Backtracking
• Decision trees
• Bit manipulation techniques

---

2. When to Use the Subsets Pattern

You should consider the Subsets pattern when the problem asks you to:

1. Generate all possible combinations or subsets of a set.
2. Explore all possible choices where each element can be included or excluded.
3. Solve decision-making problems, like selecting items for a knapsack, forming combinations, or checking possible sequences.

Problem Indicators:

• “Generate all subsets of an array”
• “Return all combinations of numbers”
• “Subset sum / combination sum problems”
• “Find all possible states or configurations”

---

3. Core Idea

The core idea is decision-based recursion:

1. At each step, for each element, decide whether to include it or not in the current subset.
2. Recursively explore both choices.
3. Add the current subset to the result list at each step.

This is a classic backtracking pattern.

---

4. Step-by-Step Example

Input: [1, 2]

Step 1: Start with empty subset []

• Decision on element 1:
  • Include 1 → [1]
    • Decision on element 2:
      • Include 2 → [1, 2]
      • Exclude 2 → [1]
  • Exclude 1 → []
    • Decision on element 2:
      • Include 2 → [2]
      • Exclude 2 → []

All subsets: [[], [1], [2], [1,2]]

Observation:
At each level, the decision tree branches into two: include or exclude the current element.

---

5. Recursive (Backtracking) Approach – Java

import java.util.*;

public class SubsetsPattern {
    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 index, List<Integer> current, List<List<Integer>> result) {
        // Add the current subset to the result
        result.add(new ArrayList<>(current));

        // Explore further elements
        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);            // Include nums[i]
            backtrack(nums, i + 1, current, result); // Recurse
            current.remove(current.size() - 1);      // Backtrack
        }
    }

    public static void main(String[] args) {
        SubsetsPattern sp = new SubsetsPattern();
        int[] nums = {1, 2, 3};
        System.out.println(sp.subsets(nums));
    }
}

Explanation:

1. current stores the current subset being built.
2. At each index, we include the element and recurse.
3. After recursion, backtrack by removing the last element.
4. Adding current at every recursion ensures all subsets are included.

Time Complexity: O(2^n × n) – There are 2^n subsets, and copying each subset of length n
Space Complexity: O(n) – Recursion stack + current subset

---

6. Iterative Approach

You can also generate subsets iteratively:

public List<List<Integer>> subsetsIterative(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>()); // start with empty subset

    for (int num : nums) {
        List<List<Integer>> newSubsets = new ArrayList<>();
        for (List<Integer> subset : result) {
            List<Integer> newSubset = new ArrayList<>(subset);
            newSubset.add(num);
            newSubsets.add(newSubset);
        }
        result.addAll(newSubsets);
    }
    return result;
}

Idea:

• Start with empty subset.
• For each number, add it to all existing subsets to form new subsets.
• Repeat for all elements.

Time Complexity: O(2^n × n)
Space Complexity: O(2^n × n)

---

7. Variants of Subset Problems

1. Subsets with duplicates – Handle duplicate numbers to avoid duplicate subsets.
   • Sort the array first
   • Skip duplicates while generating subsets
2. Subset sum problems – Generate subsets and check sum constraints.
3. Fixed-length subsets / combinations – Generate only subsets of size k.
4. Bitmasking approach – Treat each subset as a binary number, where 1 = include, 0 = exclude.

---

8. Bit Manipulation Approach

For n elements, there are 2^n subsets:

public List<List<Integer>> subsetsBitmask(int[] nums) {
    int n = nums.length;
    List<List<Integer>> result = new ArrayList<>();

    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) { // if i-th bit is set
                subset.add(nums[i]);
            }
        }
        result.add(subset);
    }
    return result;
}

Time Complexity: O(2^n × n)
Space Complexity: O(2^n × n)

---

9. When to Use Subsets Pattern

• Whenever you need to explore all combinations of elements.
• Problems often involve decision-making: include/exclude elements.
• Can be used in recursive, iterative, or bitmasking approaches.
• Often a building block for combination sum, palindrome partitions, or knapsack problems.

---

10. Edge Cases

1. Empty array → Only subset is [[]].
2. Single-element array → [[], [element]].
3. Arrays with duplicates → Sort and skip duplicates to avoid repeated subsets.
4. Large arrays → Recursive approach may lead to stack overflow; iterative approach may be preferred.

---

11. Key Takeaways

1. The Subsets pattern is a backtracking-based decision-making pattern.
2. Recursive approach builds subsets by including or excluding elements.
3. Iterative approach builds new subsets from existing ones.
4. Bitmasking uses binary representation to generate all subsets efficiently.
5. Useful for power set generation, combination problems, subset sum, and decision-tree exploration.