Permutations III

Permutations III

What is this problem about?

The Permutations III problem asks for permutations of 1..n with the additional constraint that adjacent elements must not be consecutive integers (|perm[i] - perm[i+1]| != 1). This coding problem uses backtracking with an additional adjacency constraint check. The array and backtracking interview pattern is demonstrated with pruning.

Why is this asked in interviews?

Goldman Sachs asks this to test backtracking with custom constraints. Adding the "no consecutive integers adjacent" rule requires checking the last placed element before each placement, enabling significant pruning of the search space.

Algorithmic pattern used

Backtracking with adjacency pruning. Standard permutation backtracking with an extra check: before placing nums[i] at position j > 0, verify |nums[i] - current[-1]| > 1. If the constraint fails, skip this choice. This prunes many invalid branches early.

Example explanation

n=3, nums=[1,2,3]. Standard permutations=6. With constraint |a-b|!=1:

• [1,2,3]: |1-2|=1 ✗. [1,3,2]: |1-3|=2✓, |3-2|=1 ✗.
• [2,1,3]: |2-1|=1 ✗. [2,3,1]: |2-3|=1 ✗.
• [3,1,2]: |3-1|=2✓, |1-2|=1 ✗. [3,2,1]: |3-2|=1 ✗. No valid permutation → result = [].

n=4: some valid permutations exist (e.g., [2,4,1,3]).

Common mistakes candidates make

• Not pruning early (checking constraint only at the end wastes backtracking effort).
• Using |a-b|!=1 but forgetting |b-a|!=1 (absolute value handles both).
• Off-by-one: |nums[i]-current[-1]|>1 means strictly more than 1 apart.
• Not initializing the used array correctly.

Interview preparation tip

Constraint-based backtracking always prunes as early as possible. Check the constraint before recursing, not after. The adjacency constraint here is checked immediately when adding to the path. Practice adding various constraints to standard permutation backtracking: "no two same elements adjacent," "alternating odd/even," "no two consecutive." Each requires only a minor modification to the base template.