mediumBacktrackingPattern: Backtracking
Valid Permutations with Forbidden Adjacent Pairs Solution
Problem Statement
You are given an integer `n`, representing `n` distinct items labeled from `0` to `n-1`. You are also provided with a list of `forbidden_pairs`, where each pair `[u, v]` indicates that item `u` cannot be immediately followed by item `v` in any valid permutation. Your task is to find the total number of unique permutations of all `n` items such that no `forbidden_pair` appears as adjacent elements in the permutation. Each item must be used exactly once in each permutation.
Examples
Example 1:
Input:n = 3, forbidden_pairs = [[0, 1]]
Output:4
Explanation: The items are `[0, 1, 2]`. The forbidden adjacent pair is `(0, 1)`, meaning `0` cannot be immediately followed by `1`. The `3! = 6` total permutations are:
- `[0, 1, 2]` (Invalid: 0 followed by 1)
- `[0, 2, 1]` (Valid)
- `[1, 0, 2]` (Valid)
- `[1, 2, 0]` (Valid)
- `[2, 0, 1]` (Invalid: 0 followed by 1)
- `[2, 1, 0]` (Valid)
Thus, there are 4 valid permutations.
Example 2:
Input:n = 3, forbidden_pairs = [[0, 1], [1, 2]]
Output:3
Explanation: Items are `[0, 1, 2]`. Forbidden pairs are `(0, 1)` and `(1, 2)`. Among the `3! = 6` permutations:
- `[0, 1, 2]` (Invalid: 0 followed by 1, and 1 followed by 2)
- `[0, 2, 1]` (Valid)
- `[1, 0, 2]` (Valid)
- `[1, 2, 0]` (Invalid: 1 followed by 2)
- `[2, 0, 1]` (Invalid: 0 followed by 1)
- `[2, 1, 0]` (Valid)
There are 3 valid permutations.
Constraints
- 1 <= n <= 10
- 0 <= forbidden_pairs.length <= n * (n - 1)
- 0 <= u, v < n for each [u, v] in forbidden_pairs
- u != v for each [u, v] in forbidden_pairs
- All pairs [u, v] in forbidden_pairs are unique
Time: O(N * N!) Space: O(N)
A more efficient approach uses backtracking. We build permutations incrementally, maintaining a `visited` set for items already placed. At each step, we iterate through unvisited items and, if placing an item does not form a forbidden adjacent pair with the last item placed, we recursively proceed. If a valid permutation of length `n` is formed, we count it, and then backtrack to explore other possibilities. The complexity is O(N * N!) due to exploring permutations, with O(N) space for the recursion stack and visited state.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def solve():
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
forbidden_map = {}
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
if u not in forbidden_map:
forbidden_map[u] = set()
forbidden_map[u].add(v)
count = 0
used = [False] * n
def backtrack(idx, last_item_in_perm):
nonlocal count
if idx == n:
count += 1
return
for i in range(n):
if not used[i]:
# Check forbidden pair constraint
# If it's not the first item AND [last_item_in_perm, i] is forbidden
if last_item_in_perm != -1 and last_item_in_perm in forbidden_map and i in forbidden_map[last_item_in_perm]:
continue # Skip this item as it forms a forbidden pair
used[i] = True
backtrack(idx + 1, i)
used[i] = False # Backtrack
# Start the backtracking process. -1 indicates no previous item.
backtrack(0, -1)
sys.stdout.write(str(count) + '\n')
solve()