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

"all permutations", "all orderings", "all arrangements"; every element used exactly once, order counts; each position has its own small set of options (lower/upper case)

Permutations (Backtracking Sub-pattern)

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

**Permutations** uses `used[]` and loops from 0. **Letter Case Permutation** keeps the positions fixed and branches only on letters (two options each), so it is really 2^L, like subsets. **Permutations II** has equal values: sort, and skip `nums[i]` when it equals `nums[i-1]` and `nums[i-1]` is not used, so equal copies always appear left to right.

Fill positions one at a time with an element not used yet. The order matters, so there are n! answers.

Signals in the problem statement

›
"all permutations", "all orderings", "all arrangements"
›
every element used exactly once, order counts
›
each position has its own small set of options (lower/upper case)

What makes it different

Permutations uses used[] and loops from 0. Letter Case Permutation keeps the positions fixed and branches only on letters (two options each), so it is really 2^L, like subsets. Permutations II has equal values: sort, and skip nums[i] when it equals nums[i-1] and nums[i-1] is not used, so equal copies always appear left to right.

Questions

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

1
Permutations
Basic Anchor·LeetCode #46
WalkthroughMedium
2
Letter Case Permutation
Basic Reinforcement·LeetCode #784
WalkthroughMedium
3
Permutations II
Slight Variation·LeetCode #47
WalkthroughMedium

Template

permutations-template.cpp

// Permutations: fill positions one by one with any element not used yet.
// With duplicates: sort, and use equal copies only in left-to-right order (skip if the left copy is unused).
void build(const vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& out) {
    if (path.size() == nums.size()) { out.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {         // any position: loop from 0, not from start
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // duplicate branch
        used[i] = true;  path.push_back(nums[i]);        // choose
        build(nums, used, path, out);                    // explore
        path.pop_back(); used[i] = false;                // un-choose
    }
}

vector<vector<int>> permuteUnique(vector<int> nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> out;
    vector<int> path;
    vector<bool> used(nums.size(), false);
    build(nums, used, 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?

Subsets Combinations / choose K