Definition
Subsets generation produces all possible combinations of elements from a distinct set.
- Power set is the set of all subsets, and for n distinct elements it contains exactly 2^n subsets.
- Iterative doubling starts with one empty subset and doubles the collection with each new element.
- Snapshot size must be captured before each round so newly added subsets are not processed again.
- Defensive copy of each subset prevents later rounds from mutating earlier results.
- Optimal output means the algorithm is O(n * 2^n) which is inherently required since that many subsets must be produced.
At National Bank of India, a customer like Rajesh can opt into any combination of add-on services: overdraft protection, insurance, and a rewards card. The product team wants every possible service bundle he could choose, from choosing nothing to choosing all three. They start with one empty bundle, and for each new service they copy every bundle so far and add the service to each copy, so the number of bundles doubles each time.
Understanding the Concepts
What is the Subsets Problem?
The subsets problem asks you to generate every possible combination of elements from a given set of distinct numbers, including the empty set and the full set. For n elements, there are exactly 2^n subsets. This is a foundational problem in the Subsets pattern family.
At National Bank of India, the product team wants to enumerate every possible add-on service bundle that a customer like Rajesh could choose from a list of available services.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class SubsetGenerator {
public static List<List<Integer>> generateSubsets(int[] nums) {
List<List<Integer>> subsets = new ArrayList<>();
subsets.add(new ArrayList<>()); // start with empty subset
for (int num : nums) {
int size = subsets.size(); // snapshot before adding
for (int i = 0; i < size; i++) {
List<Integer> copy = new ArrayList<>(subsets.get(i));
copy.add(num);
subsets.add(copy);
}
}
return subsets;
}
public static void main(String[] args) {
int[] serviceCodes = {101, 202, 303}; // overdraft, insurance, rewards
List<List<Integer>> bundles = generateSubsets(serviceCodes);
System.out.println("Total bundles: " + bundles.size());
for (List<Integer> bundle : bundles) {
System.out.println(bundle);
}
}
}
Total bundles: 8
[]
[101]
[202]
[101, 202]
[303]
[101, 303]
[202, 303]
[101, 202, 303]
Why Does This Problem Matter?
Subset generation is the foundation for many algorithmic problems: combination sum, subset sum, power set queries, and feature toggle enumeration. Understanding it unlocks the entire Subsets pattern family used in backtracking and dynamic programming.
In banking, Priya at HDFC needs to evaluate every combination of loan adjustment options to find the best package for a customer. Subset generation gives her the complete search space.
package com.bank.service;
import java.util.List;
public class LoanOptionEvaluator {
public static void evaluateAllBundles(List<List<String>> bundles) {
for (List<String> bundle : bundles) {
System.out.println("Evaluating bundle: " + bundle);
}
}
}
How Does the Iterative Doubling Technique Work?
The technique starts with a list containing only the empty subset. For each new element, it takes a snapshot of the current list size, then iterates over exactly that many existing subsets, copying each and appending the new element. This doubles the collection with each element.
The key detail is capturing the size before the round begins. If you iterated over the live collection while adding to it, you would process subsets you just created and over-generate.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class IterativeDoublingExplained {
public static void main(String[] args) {
List<List<String>> subsets = new ArrayList<>();
subsets.add(new ArrayList<>());
String[] services = {"Overdraft", "Insurance", "Rewards"};
for (String service : services) {
int snapshotSize = subsets.size(); // CRITICAL: snapshot before adding
System.out.println("Processing " + service + ", current count: " + snapshotSize);
for (int i = 0; i < snapshotSize; i++) {
List<String> copy = new ArrayList<>(subsets.get(i));
copy.add(service);
subsets.add(copy);
}
System.out.println("After " + service + ", count doubled to: " + subsets.size());
}
}
}
Processing Overdraft, current count: 1
After Overdraft, count doubled to: 2
Processing Insurance, current count: 2
After Insurance, count doubled to: 4
Processing Rewards, current count: 4
After Rewards, count doubled to: 8
How Is Iterative Doubling Different from Backtracking?
Both approaches produce the same result, but they differ in mechanism.
| Aspect | Iterative Doubling | Backtracking |
|---|---|---|
| Mechanism | Copy and extend existing subsets | Choose/unchoose elements recursively |
| Stack usage | No recursion, no stack growth | O(n) recursion depth |
| Code style | Loop-based, explicit list management | Recursive, implicit state on call stack |
| Duplicate handling | Requires sorting + skip for duplicates | Requires sorting + skip for duplicates |
| Ease of understanding | Concrete list manipulation | Abstract choose/explore/unchoose |
Backtracking version:
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class SubsetsBacktracking {
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current)); // record every partial subset
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1); // unchoose
}
}
}
What Are the Edge Cases?
The primary edge cases are an empty input array and an array with a single element. An empty array should produce exactly one subset: the empty set. A single-element array produces two subsets: the empty set and the set containing that one element.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class SubsetEdgeCases {
public static void main(String[] args) {
// Edge case 1: empty input
int[] empty = {};
List<List<Integer>> result1 = SubsetGenerator.generateSubsets(empty);
System.out.println("Empty input subsets: " + result1); // [[]]
System.out.println("Count: " + result1.size()); // 1
// Edge case 2: single element
int[] single = {500};
List<List<Integer>> result2 = SubsetGenerator.generateSubsets(single);
System.out.println("Single element subsets: " + result2); // [[], [500]]
System.out.println("Count: " + result2.size()); // 2
}
}
Empty input subsets: [[]]
Count: 1
Single element subsets: [[], [500]]
Count: 2
What Are the Limitations?
The output size is inherently exponential. For n elements there are 2^n subsets, so the total work is O(n * 2^n) counting the time to copy each subset. This means subset generation is only feasible for small n. For n = 20 there are about one million subsets, and for n = 30 there are about one billion.
In a banking context, if Rajesh has 25 optional services, enumerating all subsets produces over 33 million bundles, which is impractical for real-time display.
package com.bank.core;
public class SubsetFeasibility {
public static void main(String[] args) {
for (int n = 5; n <= 25; n += 5) {
long count = 1L << n; // 2^n
System.out.println("n=" + n + " -> " + count + " subsets");
}
}
}
n=5 -> 32 subsets
n=10 -> 1024 subsets
n=15 -> 32768 subsets
n=20 -> 1048576 subsets
n=25 -> 33554432 subsets
What About Duplicate Elements?
When the input contains duplicate elements, the basic iterative doubling technique produces duplicate subsets. The fix is to sort the input first, and when processing a duplicate element, only extend the subsets that were added in the previous round rather than all existing subsets.
package com.bank.core;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetsWithDuplicates {
public static List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> subsets = new ArrayList<>();
subsets.add(new ArrayList<>());
int prevSize = 0;
for (int i = 0; i < nums.length; i++) {
int start = (i > 0 && nums[i] == nums[i - 1]) ? prevSize : 0;
int size = subsets.size();
for (int j = start; j < size; j++) {
List<Integer> copy = new ArrayList<>(subsets.get(j));
copy.add(nums[i]);
subsets.add(copy);
}
prevSize = size;
}
return subsets;
}
public static void main(String[] args) {
int[] codes = {100, 200, 200}; // duplicate service code
System.out.println(subsetsWithDup(codes));
}
}
[[], [100], [200], [100, 200], [200, 200], [100, 200, 200]]
What About Bit Manipulation?
An alternative approach uses bit manipulation. Each subset corresponds to a binary number from 0 to 2^n minus 1, where each bit indicates whether an element is included.
package com.bank.core;
import java.util.ArrayList;
import java.util.List;
public class SubsetsBitmask {
public static 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) {
int[] amounts = {1000, 2000, 5000};
System.out.println(subsets(amounts));
}
}
[[], [1000], [2000], [1000, 2000], [5000], [1000, 5000], [2000, 5000], [1000, 2000, 5000]]
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask these follow-ups after the basic subsets problem:
- Handle duplicate elements (Subsets II): sort and skip duplicates as shown above.
- Generate subsets of a fixed size K (Combinations): restrict the generation to subsets of exactly K elements.
- Find subsets that sum to a target (Subset Sum): combine subset generation with a sum constraint.
- Count subsets without generating them: the answer is always 2^n for distinct elements.
package com.bank.core;
public class SubsetCount {
public static void main(String[] args) {
int n = 5; // 5 add-on services
System.out.println("Total possible bundles: " + (1 << n));
}
}
Total possible bundles: 32
Visual Overview
Iterative Doubling Process: Start: [ [] ] Add element 101 (Overdraft): ┌──────────────────────────────────┐ │ Existing: [] │ │ New: [101] │ │ Result: [], [101] │ └──────────────────────────────────┘ Add element 202 (Insurance): ┌──────────────────────────────────┐ │ Existing: [], [101] │ │ New: [202], [101,202] │ │ Result: [], [101], │ │ [202], [101,202] │ └──────────────────────────────────┘ Add element 303 (Rewards): ┌──────────────────────────────────┐ │ Existing: [], [101], │ │ [202], [101,202] │ │ New: [303], [101,303], │ │ [202,303],[101,202,303]│ │ Total: 8 subsets = 2^3 │ └──────────────────────────────────┘
Key Takeaway
Subsets is the foundational problem of the Subsets pattern: given a set of distinct elements I generate all 2^n subsets, including the empty set and the full set. I use the iterative doubling technique. I start with a collection containing only the empty subset, and for each new element I take a snapshot of the current collection size, then copy every existing subset and add the new element to each copy. Each element therefore doubles the collection, and after processing all elements I have exactly every subset.
The one detail that trips people up is capturing the size before the round begins. If I iterated over the live collection while adding to it, I would process subsets I just created and over-generate, so I snapshot the size first and extend only the pre-existing subsets. I also make each subset a fresh copy so extending subsets in a later round never mutates an earlier result.
At National Bank of India I used this to enumerate every add-on service bundle a customer like Rajesh could choose, from the empty bundle to the full bundle, so the product team could price and present all options. I generated the bundles by doubling as each service was considered, which guaranteed completeness without recursion.
The key limitation is that the output is inherently exponential. For 20 elements there are over a million subsets, and for 30 there are over a billion. The algorithm is optimal in the sense that it spends time proportional to what it must produce, but one should guard against calling it on large inputs. When duplicates are present, sorting and restricting which subsets to extend avoids over-counting.
Remember one sentence: start with the empty subset, snapshot the size, and double the collection by copying and extending with each new element.
---