许多人在学习某个知识点时，可能都会有类似的经历：虽然能理解基本概念，但在面对稍微有些变化的题目时，却感到束手无策。每当遇到这种情况，很多人都会陷入困惑，究竟有什么办法能够有效突破这一难关？
答案除了勤加练习，实际上还有一个非常有效的策略。
鲁迅先生曾经提到过，如果要学习算法，最好是集中精力在某一个特定的算法思想或数据结构上，深刻钻研一段时间。这意味着，当你学习了递归算法时，就应该持续练习递归相关的题目；学了链表，就集中刷链表相关题目。而绝对不要今天做递归，明天跳到动态规划，后天又开始研究贪心算法。新手最容易犯的错误就是以为自己了解了某个知识点，但却只是浅尝辄止，这是初学者的大忌！要做的，是对同一类型的题目进行反复练习，直到形成“肌肉记忆”，这样在将来遇到类似问题时，就能不假思索地知道该如何处理。
言归正传，排列组合是面试中常见的考察内容。虽然表面上看，排列组合的题目简单易懂，但实际上它有很多变种，难度可以随着变形逐步增加。而且，排列组合问题通常有多种解法，这让它成为评估候选人算法能力的重要考题。对于初学者而言，排列组合的递归解法比较难以理解（笔者当初反复看了好几遍代码，也一度没有搞懂）。接下来我将为大家提供一个简单易懂的递归解法，这也是本文的核心内容。
接下来，我们将通过“递归四步法”来讲解排列组合的解法，具体内容包括以下几个部分：
认识排列
排列的常见解法
理解组合
组合的递归解法
排列组合在面试中的一些常见变形
什么是排列？
排列指的是从n个不同元素中，任意选出m个（m ≤ n）元素，并将它们按照一定的顺序排列，称为从n个元素中选取m个元素的一个排列。如果m等于n，那我们称这种排列为全排列。
大家是否回忆起了高中时学过的排列公式呢？不妨举个例子，考虑数字1、2、3的全排列一共有多少种呢？
我们可以选择3个数字中的一个放在第一位，接下来，第二位只能选剩下的2个数字，第三位则只有1个数字可选。总共有 3 × 2 × 1 = 6 种排列。
既然我们知道了什么是全排列，那接下来就来看看如何用程序打印出1到n（n < 10）的全排列。
对于这道题，若没有思路，不妨先从最简单的方法着手，那就是——穷举法！
穷举法
我们可以通过列举出所有可能的情况，来求解全排列。具体来说，就是遍历每一位可能的数字，组合出所有排列，再去除重复的排列。这样，我们就能得到所需的全排列。
java
复制代码
/* 求1到n的全排列 */
public void permutation(int n) {
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
for (int k = 1; k < n + 1; k++) {
if (i != j && i != k && j != k) {
System.out.println(i + "" + j + "" + k);
}
}
}
}
看这个代码，大家一定能发现，时间复杂度非常高。三层嵌套的循环意味着时间复杂度为O(n^3)。但对于n最大为9的情况来说，总共最多需要进行9 × 9 × 9 = 729次计算，这对当前的计算机性能来说，完全不成问题。这个方法在小规模的情况下是完全可行的。
在学习过程中，我们要学会根据场景选择合适的方案。正如一句话所说，“过早的性能优化是之源”。比如一个初创公司，日活跃用户（DAU）不过千，却要引入复杂的分布式架构，这就显得过于超前。技术没有最好，只有最合适的。
这篇文章的核心目的，也是为了帮助大家理解排列组合的递归解法。很多人对递归解法感到困惑，而我自己当初也是看了很多遍才略有理解。通过我总结的“递归四步法”，大家可以更加轻松地掌握这一方法。
递归四步法解析
我们先来看一下，如何判断排列问题是否适合使用递归方法。因为如前所述，只有符合递归条件的问题，才适合用递归来求解。
看似复杂的问题，其实背后有着很明确的规律。假设我们已经确定了第一个数字（例如1），那么剩下的排列问题就转化为求余下数字的排列问题。问题规模从n缩小到n-1，且子问题与原问题有相同的解决方式。这就符合递归的条件。
递归四步法的实现
定义函数功能
我们需要定义一个函数，用来计算从某个位置开始的排列。假设数字1到n的排列已存储在数组arr中，函数将从数组的第k位开始计算排列。
java
复制代码
public void permutation(int[] arr, int k) {
// 递归的终止条件
if (k == arr.length - 1) {
System.out.println(Arrays.toString(arr));
} else {
// 交换数组元素，选取第k位
for (int i = k; i < arr.length; i++) {
swap(arr, k, i);
// 递归调用，处理剩余元素
permutation(arr, k + 1);
// 恢复交换，保持原始顺序
swap(arr, k, i);
}
}
递推公式
为了交换每个数字位置，我们需要在第k位和剩下的数字进行交换。交换完成后，对剩下的n-1个元素继续递归排列。
递归终止条件
当递归到数组的最后一位时，表示排列已经完成，打印出当前排列即可。
时间复杂度分析
上述代码的时间复杂度为O(n!)，因为全排列本身需要进行n!次操作，这个复杂度是无法避免的。
其他常见解法：字典排序法
除了递归解法，字典排序法也是常见的全排列算法。它的核心思想是从当前排列的最小值开始，按字典序递增的方式，找到下一个排列，直到排列达到最大值。
字典排序法步骤：
从右往左，寻找第一个左邻小于右邻的数字。
再从右往左，找到第一个大于第1步找到的数字的元素。
交换这两个数字。
反转第2步之后的所有元素，得到下一个排列。
字典排序法通常比递归方法更高效，尤其是在需要求解大量排列时。