Permutations And Counts

Use this when order matters. The recursion fills one position at a time by choosing from values that remain available.

Used-Array Template

Use when values are distinct or duplicate skipping by sorted index is easy.

dfs():
    if path.size == n:
        add path
        return
 
    for i = 0; i < n; i++:
        if used[i]:
            continue
 
        used[i] = true
        path.push(nums[i])
        dfs()
        path.pop()
        used[i] = false

For duplicates after sorting:

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

Uses is basically to mean that you cannot choose the 2nd copy if you haven’t chosen the first copy.

Count-Map Template

Use when repeated values make frequency-based choices cleaner than index-based choices.

dfs():
    if complete:
        add answer
        return
 
    for value in counts:
        if counts[value] == 0:
            continue
 
        counts[value]--
        path.push(value)
        dfs()
        path.pop()
        counts[value]++

Problems

Permutations

Problem: generate all permutations of distinct numbers.

Pattern: try every unused index at each position.

Optimizations: none asymptotically, because all n! permutations must be produced. A swap-based recursion can avoid a separate used array, but the used-array version is often clearer.

Permutations II

Problem: generate unique permutations when values may repeat.

Pattern: sort and skip same value at the same depth, or use counts.

Optimizations: sorting plus duplicate skip avoids duplicate branches. A count-map recursion is often cleaner when there are many repeated values because it loops over distinct values instead of all indices.

dfs():
    if path.size == n:
        ans.push(path)
        return
 
    for value in counts:
        if counts[value] == 0:
            continue
 
        counts[value]--
        path.push(value)
        dfs()
        path.pop()
        counts[value]++

Letter Tile Possibilities

Problem: count all non-empty sequences from an array of chars ( has repeated )

Pattern: choose any remaining letter count at each step; count the current choice before recursing.

Optimizations: use a frequency array or count map instead of generating strings in a set. Since only the count is needed, increment the answer when choosing a letter and avoid storing every sequence.

Beautiful Arrangement

Problem: count permutations where each value fits its position.

Pattern: fill one position at a time, choosing unused values that satisfy the divisibility rule.

Optimizations: precompute valid values for each position. For larger constraints, use bitmask DP: dp[pos][used_mask] or just memoize by used_mask.

Brace Expansion II

Problem: generate strings from nested brace expressions.

Pattern: parse first; expansion often uses set/count-style generation rather than raw index recursion.

Optimizations: this is mainly a parsing problem, not a pure backtracking one. Use sets to deduplicate and sort only at the end. Parse union and concatenation cleanly before expanding nested groups.