Problem
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.
Examples
Example 1
| |
Example 2
| |
Example 3
| |
Constraints
1 <= n <= 10
Solution
Method 1 - Backtracking (Parity Constraint)
Intuition
We generate permutations using backtracking but prune choices that would violate the parity constraint: no two adjacent elements may both be odd or both be even. This keeps the search space small by avoiding invalid partial permutations early.
Approach
Use a recursive backtracking function that builds a permutation by adding unused numbers at each step, skipping numbers that would make the last two elements have the same parity. When the permutation is complete (length n), add it to the result.
Code
| |
| |
| |
| |
| |
| |
| |
Complexity
- ⏰ Time complexity:
O(n!)– There are up ton!permutations in the worst case; generating each permutation takes O(n) overall work across the recursion but the dominant factor isn!. - 🧺 Space complexity:
O(n!)– Storing all permutations can take up ton!arrays of lengthn; recursion stack uses O(n) additional space.