Explanation

We can solve this problem recursively. At every index, we look for the smallest number that satisfies the asked condition (i.e., there are no adjacent elements whose difference is 1) and if it satisfies, we add it to our permutation.

For $n = 2$ and $n = 3$, we know that no permutation satisfies the asked condition.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <iostream>
#include <set>
#include <vector>

std::vector<int> res;
std::set<int> ele;

void backtrack(int n) {
	if ((int)res.size() == n) {
		for (int x : res) { std::cout << x << " \n"[x == res.back()]; }