← All patterns
Subsets
DFS enumeration of subsets, permutations, and combinations. Start-index for combinations; in-place swap for permutations; sort-and-skip for dedup on duplicate inputs.
8 problems
8 Medium
Enumerate every subset, permutation, or combination of an input. DFS with backtracking is the standard structure; only the branching policy differs. Subsets: include/exclude at each index (or iterative 'double' on each new element). Permutations: swap each remaining element into position. Combinations: pick from `start` onwards to avoid reorderings.
Duplicates are handled with sort + 'skip identical-to-previous at the same recursion level' — never globally, or you'll miss valid subsets where the duplicate is needed.
When to reach for this pattern
- Output is all subsets, all permutations, or all combinations
- Generate all valid expressions / configurations matching constraints
- Enumerate decisions where each item is independently in/out
- Letter case toggles, phone-number letter combinations
Canonical template
// subsets with dedup
sort(nums.begin(), nums.end());
vector<vector<int>> out;
vector<int> path;
function<void(int)> dfs = [&](int start) {
out.push_back(path);
for (int i = start; i < (int)nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue;
path.push_back(nums[i]);
dfs(i + 1);
path.pop_back();
}
};
dfs(0);C++ · adapt the names and types to your problem.
Common pitfalls
- Skipping dedup logic on inputs with duplicates produces duplicate subsets
- Forgetting
path.pop_back()after recursion — corrupts subsequent branches - Pass-by-value path (no pop needed) vs pass-by-reference path (must pop) — pick one and stick to it
- Combinations: passing
i(reuse) vsi + 1(no reuse) controls whether the same item is reusable
Related patterns
Problems (8)
- Medium
- Medium
- Medium
- Medium
- Medium
- Medium
- Medium
- Medium