What signals in a problem statement indicate the Subsets sub-pattern?

"all subsets", "power set"; "every possible selection" of the elements; a total over all subsets (sum, XOR) with n ≤ 12

Subsets (Backtracking Sub-pattern)

Q: What makes Subsets different from other sub-patterns?

**Subsets** is the plain template; the bitmask loop over 2ⁿ masks gives the same answers. **Sum of All Subset XOR Totals** first carries the running XOR down the recursion, then drops the recursion entirely: each bit that appears in any number is set in exactly half of the subsets, so the answer is `OR of all × 2ⁿ⁻¹`. **Subsets II** has equal values: sort and skip equal neighbours at the same depth.

Every element is either in or out, so there are 2ⁿ subsets. Build them with a start index; every call is one subset.

Signals in the problem statement

›
"all subsets", "power set"
›
"every possible selection" of the elements
›
a total over all subsets (sum, XOR) with n ≤ 12

What makes it different

Subsets is the plain template; the bitmask loop over 2ⁿ masks gives the same answers. Sum of All Subset XOR Totals first carries the running XOR down the recursion, then drops the recursion entirely: each bit that appears in any number is set in exactly half of the subsets, so the answer is OR of all × 2ⁿ⁻¹. Subsets II has equal values: sort and skip equal neighbours at the same depth.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Subsets
Basic Anchor·LeetCode #78
WalkthroughMedium
2
Sum of All Subset XOR Totals
Basic Reinforcement·LeetCode #1863
WalkthroughEasy
3
Subsets II
Slight Variation·LeetCode #90
WalkthroughMedium

Template

subsets-template.cpp

// Subsets: every call is one subset; the loop picks the NEXT element to add, always to the right.
// Sort first and skip equal neighbours at the same depth to avoid duplicate subsets (Subsets II).
void build(const vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& out) {
    out.push_back(path);                                 // every node of the tree is an answer
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) continue; // same value already tried at this depth
        path.push_back(nums[i]);                         // choose
        build(nums, i + 1, path, out);                   // explore: only elements to the right
        path.pop_back();                                 // un-choose
    }
}

vector<vector<int>> subsetsWithDup(vector<int> nums) {
    sort(nums.begin(), nums.end());                      // equal values side by side
    vector<vector<int>> out;
    vector<int> path;
    build(nums, 0, path, out);
    return out;
}

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Backtracking overview Permutations