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 <= 10We 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.
Java
C++
Go
TypeScript
Practice Permutations III with our built-in code editor and test cases.
Practice on FleetCode