Subsets Pattern in Backtracking
The Problem
Given a collection of values, produce every subset — every way to pick some of them (including none and all).
Input: [1, 2, 3] Subsets (8 = 2³): [] [1] [2] [3] [1, 2] [1, 3] [2, 3] [1, 2, 3] Order inside a subset does not matter: [1, 2] and [2, 1] are the same subset.
Subsets are the foundation for many other searches. "Choose a team", "pick items for a bag", "select features to enable" — all of them are subsets plus an extra rule.
Method 1: Take / Skip
One level per element, two branches each: put it in or leave it out. Answers sit at the leaves.
Level 0 decides 1, level 1 decides 2, level 2 decides 3:
[]
take 1 / \ skip 1
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []
Method 2: Pick-Next (Start Index)
Each node already is a subset. From a node, add any element after the last one picked.
[]
/ | \
[1] [2] [3]
/ \ |
[1,2] [1,3] [2,3]
|
[1,2,3]
Record at every node → 8 nodes, 8 subsets, no wasted calls.
Method 3: Bitmask (No Recursion)
Number the elements 0 … n−1. Every integer mask from 0 to 2ⁿ − 1 describes one subset: bit i is 1 ⇔ element i is included.
nums = [1, 2, 3] mask binary subset 0 000 [] 1 001 [1] 2 010 [2] 3 011 [1, 2] 4 100 [3] 5 101 [1, 3] 6 110 [2, 3] 7 111 [1, 2, 3]
Bitmasks are compact and fast for n ≤ about 20, but they cannot prune — every mask is built in full.
Handling Duplicate Values
With input [2, 1, 2], the plain methods produce [1, 2] twice (once with each 2). To list each distinct subset once:
STEP 1: Sort → [1, 2, 2] (equal values become neighbours)
STEP 2: In the pick-next loop, at one level, never start a branch
with the same value twice:
for j in start .. n-1:
if j > start and nums[j] == nums[j-1]:
continue ← same value already tried at this level
...
Why it works — the tree for [1, 2, 2]:
[]
/ | \
[1] [2] ✂ [2] ← second 2 at level 0: same subtree as first
/ \ |
[1,2] ✂[1,2] [2,2] ← second 2 under [1]: skipped
|
[1,2,2]
Distinct subsets: [] [1] [1,2] [1,2,2] [2] [2,2] → 6
The check is j > start, not j > 0. The first copy at each level is always allowed — that is how [2, 2] gets built (first 2 at level 0, second 2 at level 1).
Code: All Three Methods + Duplicates
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Subsets {
// Method 1 — take / skip, answers at the leaves
static void takeSkip(int[] nums, int i, List<Integer> path, List<List<Integer>> out) {
if (i == nums.length) { out.add(new ArrayList<>(path)); return; }
path.add(nums[i]); // take
takeSkip(nums, i + 1, path, out);
path.remove(path.size() - 1); // undo
takeSkip(nums, i + 1, path, out); // skip
}
// Method 2 — pick-next, every node is an answer
static void pickNext(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
out.add(new ArrayList<>(path));
for (int j = start; j < nums.length; j++) {
path.add(nums[j]);
pickNext(nums, j + 1, path, out);
path.remove(path.size() - 1);
}
}
// Method 3 — bitmask, no recursion
static List<List<Integer>> bitmask(int[] nums) {
List<List<Integer>> out = new ArrayList<>();
int n = nums.length;
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> sub = new ArrayList<>();
for (int i = 0; i < n; i++)
if ((mask & (1 << i)) != 0) sub.add(nums[i]);
out.add(sub);
}
return out;
}
// Distinct subsets when values repeat — input must be sorted first
static void distinct(int[] nums, int start, List<Integer> path, List<List<Integer>> out) {
out.add(new ArrayList<>(path));
for (int j = start; j < nums.length; j++) {
if (j > start && nums[j] == nums[j - 1]) continue; // same value, same level
path.add(nums[j]);
distinct(nums, j + 1, path, out);
path.remove(path.size() - 1);
}
}
static void show(String label, List<List<Integer>> subsets) {
StringBuilder sb = new StringBuilder(label + " (" + subsets.size() + "):");
for (List<Integer> s : subsets) sb.append(" ").append(s);
System.out.println(sb);
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
List<List<Integer>> a = new ArrayList<>(), b = new ArrayList<>();
takeSkip(nums, 0, new ArrayList<>(), a);
pickNext(nums, 0, new ArrayList<>(), b);
show("take/skip", a);
show("pick-next", b);
show("bitmask ", bitmask(nums));
int[] dup = {2, 1, 2};
List<List<Integer>> naive = new ArrayList<>(), unique = new ArrayList<>();
pickNext(dup, 0, new ArrayList<>(), naive);
Arrays.sort(dup);
distinct(dup, 0, new ArrayList<>(), unique);
show("dup naive", naive);
show("distinct ", unique);
}
}Output:
take/skip (8): [1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] []
pick-next (8): [] [1] [1, 2] [1, 2, 3] [1, 3] [2] [2, 3] [3]
bitmask (8): [] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3]
dup naive (8): [] [2] [2, 1] [2, 1, 2] [2, 2] [1] [1, 2] [2]
distinct (6): [] [1] [1, 2] [1, 2, 2] [2] [2, 2]
Look at the dup naive line: [2] appears twice and [2, 1] / [1, 2] are the same subset in a different order. Sorting plus the same-level skip removes all of that.
Adding a Rule: Subsets With a Budget
Most real tasks are "subsets, but only the ones that satisfy X". The recursive methods make this easy because the rule can be checked while building.
Task: every subset of [4, 1, 3, 2] whose sum is at most 5.
Sort first → [1, 2, 3, 4], then in the pick-next loop:
if running_sum + nums[j] > 5:
break ← not just continue: every later value is even larger
Tree (node = subset with its running sum, ✂ = loop stopped by the budget):
[] 0
├── [1] 1
│ ├── [1,2] 3 ✂ next would be 3+3 = 6
│ ├── [1,3] 4 ✂ next would be 4+4 = 8
│ └── [1,4] 5
├── [2] 2
│ ├── [2,3] 5 ✂ next would be 5+4 = 9
│ └── ✂ 2+4 = 6
├── [3] 3 ✂ next would be 3+4 = 7
└── [4] 4
Answers: [] [1] [1,2] [1,3] [1,4] [2] [2,3] [3] [4] → 9 subsets
Sorting turns continue into break: once one value is too large, every value after it is too, so the rest of the loop is skipped in one step.
Where the Subsets Pattern Appears
"Pick any group of items where ..." → subsets + rule
"Split items into two groups so that ..." → each item: group A or group B
"Is there a selection that sums to T?" → subsets + sum pruning
(or DP if only yes/no is needed)
"Enable some of these n feature flags ..." → bitmask over n ≤ 20 flags
"List every distinct selection" (repeats) → sort + same-level skip
Practice problems tagged Backtracking are collected in the problems list.
Common Mistakes
Recording at the wrong place. Take/skip records only at i == n. Pick-next records at every node. Mixing the two produces duplicates or missing subsets.
Using j > 0 instead of j > start for duplicates. That blocks the second copy of a value everywhere, so [2, 2] is never produced.
Forgetting to sort before deduplicating. The same-level skip only compares neighbours. Unsorted, [2, 1, 2] has no adjacent equal pair and nothing is skipped.
Using a set of lists to remove duplicates afterwards. It works, but it still generates every duplicate first — slower, and in Java/C++ requires the inner lists to be sorted for equality to work.
Interview Questions
Q: Compare the three ways to generate subsets.
Take/skip mirrors the definition (each element in or out) and is the easiest to extend with per-element choices. Pick-next records at every node, needs half as many calls, and is the natural base for combinations and for duplicate skipping. The bitmask loop needs no recursion and is handy for n ≤ 20 or when subsets index into a DP table, but it cannot prune.
Q: Why does sorting plus j > start && nums[j] == nums[j-1] remove exactly the duplicates and nothing else?
At one level of the pick-next tree, two equal values would start two identical subtrees, because the remaining suffixes after them contain the same multiset of values. Skipping the later sibling keeps one copy of each subtree. Choosing the second equal value as a child (deeper level) is still allowed, so subsets that genuinely contain the value twice are kept.
Q: What is the time complexity of listing all distinct subsets of an array with duplicates?
Still O(n · 2ⁿ) in the worst case (when all values are distinct), plus O(n log n) for sorting. With many duplicates the real count is smaller: the number of distinct subsets is the product of (count of each value + 1).
Summary
- ›n distinct elements have 2ⁿ subsets; listing them costs O(n · 2ⁿ).
- ›Take/skip: one level per element, record at leaves.
- ›Pick-next: start index, record at every node — the base for combinations.
- ›Bitmask: loop over 0 … 2ⁿ − 1; fast and simple but no pruning.
- ›Duplicates: sort, then skip
nums[j] == nums[j-1]whenj > start. - ›Add rules by checking them as you build, and use
breakwhen sorting guarantees later options are worse.
Next, Permutations switches from "which items" to "in what order" — where every element must appear exactly once in each answer.
How many subsets does a set of 5 distinct elements have?