Permutations III

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

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

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

C++

#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
    vector<vector<int>> permute(int n) {
        vector<vector<int>> res;
        vector<int> path;
        vector<int> used(n+1, 0);
        function<void()> dfs = [&]() {
            if (path.size() == (size_t)n) { res.push_back(path); return; }
            for (int i = 1; i <= n; ++i) {
                if (used[i]) continue;
                if (!path.empty()) {
                    int last = path.back();
                    if ((last % 2) == (i % 2)) continue; // parity constraint
                }
                used[i] = 1; path.push_back(i);
                dfs();
                path.pop_back(); used[i] = 0;
            }
        };
        dfs();
        return res;
    }
};

Go

package main

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 }
            if len(path) > 0 {
                last := path[len(path)-1]
                if last%2 == i%2 { continue }
            }
            used[i] = true
            path = append(path, i)
            dfs()
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    dfs()
    return res
}

Java

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;
            if (!path.isEmpty()) {
                int last = path.get(path.size()-1);
                if ((last % 2) == (i % 2)) continue;
            }
            used[i] = true; path.add(i);
            dfs(n, path, used, res);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}

Kotlin

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
                if (path.isNotEmpty()) {
                    val last = path.last()
                    if (last % 2 == i % 2) continue
                }
                used[i] = true
                path.add(i)
                dfs()
                path.removeLast()
                used[i] = false
            }
        }
        dfs()
        return res
    }
}

Python

from typing import List
class Solution:
    def permute(self, n: int) -> List[List[int]]:
        res: List[List[int]] = []
        path: List[int] = []
        used = [False] * (n+1)
        def dfs() -> None:
            if len(path) == n:
                res.append(path[:])
                return
            for i in range(1, n+1):
                if used[i]:
                    continue
                if path and (path[-1] % 2) == (i % 2):
                    continue
                used[i] = True
                path.append(i)
                dfs()
                path.pop()
                used[i] = False
        dfs()
        return res

Rust

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; }
            if !path.is_empty() {
                let last = *path.last().unwrap();
                if last % 2 == i % 2 { 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

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

Complexity

• ⏰ Time complexity: O(n!) – There are up to n! permutations in the worst case; generating each permutation takes O(n) overall work across the recursion but the dominant factor is n!.
• 🧺 Space complexity: O(n!) – Storing all permutations can take up to n! arrays of length n; recursion stack uses O(n) additional space.