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

1
2
3

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

1
2
3

Input: n = 2

Output: [[1,2],[2,1]]

Example 3

1
2
3

Input: n = 3

Output: [[1,2,3],[3,2,1]]

Constraints

  • 1 <= n <= 10

Solution

Intuition

This is the classic permutations problem. We can use backtracking to generate all possible orderings of the numbers 1 to n.

Approach

Use a recursive backtracking function that builds up a permutation by adding unused numbers at each step. When the permutation is complete (length n), add it to the result.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> permute(int n) {
        vector<vector<int>> res;
        vector<int> path, used(n+1, 0);
        function<void()> dfs = [&]() {
            if (path.size() == n) { res.push_back(path); return; }
            for (int i = 1; i <= n; ++i) {
                if (used[i]) continue;
                used[i] = 1; path.push_back(i);
                dfs();
                path.pop_back(); used[i] = 0;
            }
        };
        dfs();
        return res;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func permute(n int) [][]int {
    var res [][]int
    var path []int
    used := make([]bool, n+1)
    var dfs func()
    dfs = func() {
        if len(path) == n {
            tmp := make([]int, n)
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i := 1; i <= n; i++ {
            if used[i] { continue }
            used[i] = true
            path = append(path, i)
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public List<List<Integer>> permute(int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[n+1];
        dfs(n, path, used, res);
        return res;
    }
    private void dfs(int n, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (path.size() == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (used[i]) continue;
            used[i] = true; path.add(i);
            dfs(n, path, used, res);
            path.remove(path.size()-1); used[i] = false;
        }
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun permute(n: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        val path = mutableListOf<Int>()
        val used = BooleanArray(n+1)
        fun dfs() {
            if (path.size == n) {
                res.add(path.toList())
                return
            }
            for (i in 1..n) {
                if (used[i]) continue
                used[i] = true
                path.add(i)
                dfs()
                path.removeAt(path.size-1)
                used[i] = false
            }
        }
        dfs()
        return res
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def permute(n: int) -> list[list[int]]:
    res = []
    path = []
    used = [False] * (n+1)
    def dfs():
        if len(path) == n:
            res.append(path[:])
            return
        for i in range(1, n+1):
            if used[i]: continue
            used[i] = True
            path.append(i)
            dfs()
            path.pop()
            used[i] = False
    dfs()
    return res
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

fn permute(n: usize) -> Vec<Vec<usize>> {
    fn dfs(n: usize, path: &mut Vec<usize>, used: &mut Vec<bool>, res: &mut Vec<Vec<usize>>) {
        if path.len() == n {
            res.push(path.clone());
            return;
        }
        for i in 1..=n {
            if used[i] { continue; }
            used[i] = true;
            path.push(i);
            dfs(n, path, used, res);
            path.pop();
            used[i] = false;
        }
    }
    let mut res = vec![];
    let mut path = vec![];
    let mut used = vec![false; n+1];
    dfs(n, &mut path, &mut used, &mut res);
    res
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

function permute(n: number): number[][] {
    const res: number[][] = [];
    const path: number[] = [];
    const used = Array(n+1).fill(false);
    function dfs() {
        if (path.length === n) {
            res.push([...path]);
            return;
        }
        for (let i = 1; i <= n; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push(i);
            dfs();
            path.pop();
            used[i] = false;
        }
    }
    dfs();
    return res;
}

Complexity

  • ⏰ Time complexity: O(n!) (there are n! permutations, each takes O(n) to build)
  • 🧺 Space complexity: O(n!) (for storing all permutations)