题目：首位为偶数的全排列

题目描述

给定一个正整数 n，请你输出所有由数字 1 到 n 组成的 全排列，并满足以下额外条件：

排列的第一个数必须是偶数。

排列中每个数字 恰好出现一次。

请按任意顺序输出所有满足条件的排列。

输入格式

输入一行，一个整数 n。

输出格式

输出若干行，每行一个合法的排列，数字之间用一个空格隔开。

数据范围

• 1 ≤ n ≤ 9

说明：

• n ≤ 9 保证全排列总数在可接受范围内
• 本题重点在 搜索 + 剪枝，而非输出顺序

样例输入

3

样例输出（示例之一）

2 1 3
2 3 1

解释：

• 所有 1~3 的全排列共有 6 种
• 只有以偶数 2 开头的排列符合要求

样例输入

4

样例输出（示例之一）

2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

提示

• 本题可以使用 回溯 / DFS 枚举排列

• 在递归的第一层（第 0 位）进行剪枝：

  • 如果当前选择的数是奇数，直接跳过

• 该剪枝可以将搜索规模从 n! 降为约 (n/2) × (n-1)!

题目标签

• 回溯
• DFS
• 全排列
• 剪枝

教学补充

不是所有剪枝都发生在“深层”， 有些剪枝发生在“第一步”，收益最大。