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.

Python3JavaC++GoTypeScript

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

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;
    }
};

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;
}

Comments