Welcome to Subscribe On Youtube
3437. Permutations III 🔒
Description
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 <= 10
Solutions
Solution 1: Backtracking
We design a function $\textit{dfs}(i)$, which represents filling the $i$-th position, with position indices starting from $0$.
In $\textit{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.
-
class Solution { private List<int[]> ans = new ArrayList<>(); private boolean[] vis; private int[] t; private int n; public int[][] permute(int n) { this.n = n; t = new int[n]; vis = new boolean[n + 1]; dfs(0); return ans.toArray(new int[0][]); } private void dfs(int i) { if (i >= n) { ans.add(t.clone()); return; } for (int j = 1; j <= n; ++j) { if (!vis[j] && (i == 0 || t[i - 1] % 2 != j % 2)) { vis[j] = true; t[i] = j; dfs(i + 1); vis[j] = false; } } } } -
class Solution { public: vector<vector<int>> permute(int n) { vector<vector<int>> ans; vector<bool> vis(n); vector<int> t; auto dfs = [&](this auto&& dfs, int i) -> void { if (i >= n) { ans.push_back(t); return; } for (int j = 1; j <= n; ++j) { if (!vis[j] && (i == 0 || t[i - 1] % 2 != j % 2)) { vis[j] = true; t.push_back(j); dfs(i + 1); t.pop_back(); vis[j] = false; } } }; dfs(0); return ans; } }; -
class Solution: def permute(self, n: int) -> List[List[int]]: def dfs(i: int) -> None: if i >= n: ans.append(t[:]) return for j in range(1, n + 1): if not vis[j] and (i == 0 or t[-1] % 2 != j % 2): t.append(j) vis[j] = True dfs(i + 1) vis[j] = False t.pop() ans = [] t = [] vis = [False] * (n + 1) dfs(0) return ans -
func permute(n int) (ans [][]int) { vis := make([]bool, n+1) t := make([]int, n) var dfs func(i int) dfs = func(i int) { if i >= n { ans = append(ans, slices.Clone(t)) return } for j := 1; j <= n; j++ { if !vis[j] && (i == 0 || t[i-1]%2 != j%2) { vis[j] = true t[i] = j dfs(i + 1) vis[j] = false } } } dfs(0) return } -
function permute(n: number): number[][] { const ans: number[][] = []; const vis: boolean[] = Array(n).fill(false); const t: number[] = Array(n).fill(0); const dfs = (i: number) => { if (i >= n) { ans.push([...t]); return; } for (let j = 1; j <= n; ++j) { if (!vis[j] && (i === 0 || t[i - 1] % 2 !== j % 2)) { vis[j] = true; t[i] = j; dfs(i + 1); vis[j] = false; } } }; dfs(0); return ans; }