Given an integer n, an alternating permutation is a permutation of the first n positive integers such that no two adjacent elements are both odd or both even.
Return all such alternating permutations sorted in lexicographical order.
Example 1:
Input: n = 4
Output: [[1,2,3,4],[1,4,3,2],[2,1,4,3],[2,3,4,1],[3,2,1,4],[3,4,1,2],[4,1,2,3],[4,3,2,1]]
Example 2:
Input: n = 2
Output: [[1,2],[2,1]]
Example 3:
Input: n = 3
Output: [[1,2,3],[3,2,1]]
Constraints:
1 <= n <= 10Problem Overview: Generate all permutations of numbers 1..n such that every pair of adjacent elements has different parity. In other words, an odd number must be followed by an even number and vice versa.
Approach 1: Brute Force Permutation + Validation (O(n! * n) time, O(n) space)
Generate every permutation of 1..n and check whether it satisfies the parity condition. For each permutation, iterate through the array and verify that perm[i] % 2 != perm[i+1] % 2. If any adjacent pair has the same parity, discard it. This approach is straightforward but inefficient because it explores all n! permutations even though most will be invalid. The validation step adds an additional O(n) scan per permutation.
Approach 2: Backtracking with Parity Pruning (O(n! * n) time, O(n) space)
Use backtracking to build permutations incrementally. Maintain a used array to track which numbers are already placed. When choosing the next number, check the last element in the current path. Only place a number if its parity differs from the previous value. This pruning avoids generating invalid permutations early in the search tree. The recursion explores only feasible branches, which reduces the constant factor compared to brute force while still having a worst‑case complexity of O(n! * n).
The algorithm works well because the constraint is local. You only need to compare the candidate value with the previous element in the current permutation. Each recursive call appends a valid number, marks it as used, and continues exploring until the permutation length reaches n. Store each valid permutation in the result list.
This pattern appears frequently in permutation problems involving constraints. The combination of a path array and a boolean used structure is a standard technique for problems involving arrays and backtracking. Constraint checks placed before recursion dramatically reduce unnecessary exploration.
Recommended for interviews: Backtracking with pruning is the expected solution. Brute force shows you understand permutation generation, but pruning based on parity demonstrates the ability to reduce the search space during recursion.
We design a function dfs(i), which represents filling the i-th position, with position indices starting from 0.
In dfs(i), if i geq n, it means all positions have been filled, and we add the current permutation to the answer array.
Otherwise, we enumerate the numbers j that can be placed in the current position. If j has not been used and j has a different parity from the last number in the current permutation, we can place j in the current position and continue to recursively fill the next position.
The time complexity is O(n times n!), and the space complexity is O(n). Here, n is the length of the permutation.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutation + Validation | O(n! * n) | O(n) | When demonstrating basic permutation generation before applying constraints |
| Backtracking with Parity Pruning | O(n! * n) | O(n) | General case; avoids exploring invalid permutations early |
Practice Permutations III with our built-in code editor and test cases.
Practice on FleetCode