Definition
- Power set – the collection of all subsets of a set, including the empty set and the full set.
- Count – a set of n elements has exactly 2^n subsets.
- Backtracking – walk elements in order; at each element, branch into include and exclude. Each path from start to end is one subset.
- Recording – record the path at every call (not just leaves), because every prefix of choices is a valid subset.
- Copy rule – always store
new ArrayList<>(path)when recording, since the path mutates. - Complexity – O(n * 2^n) time and O(n * 2^n) space for the output.
Imagine the National Bank of India offers n optional add-on services on an account, and Priya wants to see every possible combination, from choosing nothing to choosing everything. A clerk goes through the add-ons one at a time, and for each one she branches into two worlds: one where the customer takes it and one where she skips it. Every distinct sequence of take-or-skip choices is one possible service package.
Understanding the Concepts
What is the Power Set problem?
Given a set of n distinct elements, generate all possible subsets, also called the power set. A set of n elements has exactly 2^n subsets, including the empty set and the full set.
This is LeetCode 78.
package com.bank.service;
// Input: [1, 2, 3]
// Output: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
// Count: 2^3 = 8 subsets
How does the backtracking approach work?
Use a start index and a running path list. At every recursive call, first record the current path as a valid subset. Then loop from the start index, and for each element add it to the path, recurse with the next index, and remove it to backtrack.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class Subsets {
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)); // record a COPY
for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // include
backtrack(nums, i + 1, path, result); // recurse
path.remove(path.size() - 1); // exclude (backtrack)
}
}
public static void main(String[] args) {
Subsets solver = new Subsets();
System.out.println(solver.subsets(new int[]{1, 2, 3}));
}
}
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Why record at every call, not just at leaves?
Every prefix of choices is itself a complete subset. The empty path at the very first call is the empty subset. After adding element 1, the path [1] is the subset {1}. After adding 1 and 2, [1,2] is {1,2}. Recording at every call captures all subsets, while recording only at leaves would miss all subsets shorter than n.
package com.bank.service;
public class RecordingExplanation {
// Recursion tree for [1, 2, 3]:
// Call 1: path=[] -> record []
// Call 2: path=[1] -> record [1]
// Call 3: path=[1,2] -> record [1,2]
// Call 4: path=[1,2,3] -> record [1,2,3] (leaf)
// Call 5: path=[1,3] -> record [1,3] (leaf)
// Call 6: path=[2] -> record [2]
// Call 7: path=[2,3] -> record [2,3] (leaf)
// Call 8: path=[3] -> record [3] (leaf)
}
Why must you store a copy?
The path list is mutated throughout the search. If you stored the reference directly with result.add(path), every recorded entry would point to the same object and reflect its final empty state. Always use result.add(new ArrayList<>(path)).
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class CopyBugDemo {
public static void main(String[] args) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(1);
result.add(path); // WRONG: stores reference
result.add(new ArrayList<>(path)); // CORRECT: stores copy
path.add(2);
System.out.println("Reference: " + result.get(0)); // [1, 2] - mutated!
System.out.println("Copy: " + result.get(1)); // [1] - safe
}
}
Reference: [1, 2]
Copy: [1]
What are the alternative approaches?
Three methods produce the same power set:
| Approach | Description | Best for |
|---|---|---|
| Backtracking | Recursive add-recurse-remove | Constrained variants (size limits, duplicates) |
| Iterative cascade | For each element, copy all existing subsets and add the element | Simple iterative code |
| Bitmask | Each integer 0 to 2^n-1 is a subset; bit i = include element i | Very compact |
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class SubsetsBitmask {
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
int total = 1 << n; // 2^n
List<List<Integer>> result = new ArrayList<>();
for (int mask = 0; mask < total; mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
subset.add(nums[i]);
}
}
result.add(subset);
}
return result;
}
public static void main(String[] args) {
SubsetsBitmask solver = new SubsetsBitmask();
System.out.println(solver.subsets(new int[]{1, 2, 3}));
}
}
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
What are the edge cases?
- Empty input: one subset, the empty set.
- Single element: two subsets,
[]and[element]. - Large n: 2^n grows fast; n = 20 gives about a million subsets.
package com.bank.service;
public class SubsetEdgeCases {
public static void main(String[] args) {
Subsets solver = new Subsets();
System.out.println("Empty: " + solver.subsets(new int[]{}));
System.out.println("Single: " + solver.subsets(new int[]{5}));
}
}
Empty: [[]]
Single: [[], [5]]
How do you handle duplicates (Subsets II)?
If the input contains duplicates (LeetCode 90), sort first and skip a candidate when it equals the previous one at the same recursion level. This prevents generating identical subsets.
package com.bank.service;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetsWithDuplicates {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(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++) {
if (i > start && nums[i] == nums[i - 1]) continue; // skip dup
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
SubsetsWithDuplicates solver = new SubsetsWithDuplicates();
System.out.println(solver.subsetsWithDup(new int[]{1, 2, 2}));
}
}
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
What about the banking domain use case?
At the National Bank of India, the marketing team needs every possible combination of optional account add-on services to create pricing packages. The backtracking generates all 2^n combinations, from the empty package to the full bundle.
package com.bank.service;
import java.util.List;
public class ServicePackageGenerator {
public static void main(String[] args) {
String[] services = {"OverdraftProtection", "ChequeBook", "OnlineBanking"};
int[] indices = {0, 1, 2};
Subsets solver = new Subsets();
List<List<Integer>> packages = solver.subsets(indices);
System.out.println("Service packages (" + packages.size() + " total):");
for (List<Integer> pkg : packages) {
StringBuilder sb = new StringBuilder(" {");
for (int i = 0; i < pkg.size(); i++) {
if (i > 0) sb.append(", ");
sb.append(services[pkg.get(i)]);
}
sb.append("}");
System.out.println(sb);
}
}
}
Service packages (8 total):
{}
{OverdraftProtection}
{OverdraftProtection, ChequeBook}
{OverdraftProtection, ChequeBook, OnlineBanking}
{OverdraftProtection, OnlineBanking}
{ChequeBook}
{ChequeBook, OnlineBanking}
{OnlineBanking}
What are common interview follow-up questions?
- How many subsets are there? (2^n for n distinct elements.)
- What if there are duplicates? (Sort and skip consecutive duplicates at the same level: Subsets II.)
- Can you do it without recursion? (Yes, bitmask or iterative cascade.)
- Why do you record at every call? (Every prefix is a valid subset, not just full-length ones.)
- Why do you copy the path? (The path mutates; storing the reference would corrupt all recorded subsets.)
Visual Overview
Subset Generation: Backtracking for [1, 2, 3]
backtrack(start=0, path=[])
├── record []
├── i=0: path=[1]
│ ├── record [1]
│ ├── i=1: path=[1,2]
│ │ ├── record [1,2]
│ │ └── i=2: path=[1,2,3]
│ │ └── record [1,2,3]
│ └── i=2: path=[1,3]
│ └── record [1,3]
├── i=1: path=[2]
│ ├── record [2]
│ └── i=2: path=[2,3]
│ └── record [2,3]
└── i=2: path=[3]
└── record [3]
Total: 8 subsets = 2^3
Key Takeaway
The power set is the collection of all subsets of a set, and a set of n elements has exactly 2^n subsets including the empty set. Backtracking generates them by walking elements in order and branching into include or exclude at each element. The add-recurse-remove rhythm at each step is the essence of backtracking.
The key detail is that you record the path at every recursive call, not just at leaves, because every prefix of choices is a valid subset. The empty path at the first call captures the empty subset. Always store a copy of the path when recording, because the path is mutated throughout the search.
Starting the loop at the current index prevents generating the same subset in different orders. For inputs with duplicates, sort first and skip consecutive equal values at the same recursion level. The bitmask alternative is extremely compact but backtracking generalizes best to constrained variants.
At the National Bank of India, the marketing team used this to enumerate every possible combination of optional account services for pricing and bundling. The start-index discipline guaranteed each package appeared exactly once.
Remember one sentence: record at every call, copy the path, start at the current index, and you get all 2^n subsets.
---