责编 | Elle
序言
上一篇「一文学会递归解题」一文颇受大家好评，各大号纷纭转载，让笔者颇感欣慰，不过笔者把稳到后台有读者有如下反馈
确实，相信很多人（包括我自己）都有类似的感慨，对某个知识点，看确实是看懂了，但如果真的再用同样的套路再去解一些带有同样解题思路，但稍加变形的题，每每会束手无策。对这种情形有啥好的办理办法吗？
除了勤加练习，还有一善策！
鲁迅师长西席说：如果学习算法，最好一段韶光内只刷某种算法思想或某种数据构造的题，啥意思呢?比如说你上次学了递归，那就持续找递归的题来刷，学了链表，这段韶光就专门刷链表的题，千万不可本日刷递归，来日诰日刷动态方案，后天又开始学习贪心算法。。。新手最怕的便是以为自己懂了，浅尝辄止，这是新手的大忌！
一定要对同一类型的题穷追猛打，形成肌肉影象，这样之后再碰到同一类型的题就会条件反射地一看:哦,这题用 xxx 思想该当可以靠谱。
言归正转，排列组合是口试中的热门考点由于看似大略的排列组合可以有挺多的变形，根据变形，难度可以逐渐递增，而且排列组合本身有挺多的解法，能很好地区分一个侯选者的算法水平，排列组合如果用递归挺不随意马虎理解的（反正笔者一开始看了好几遍代码愣是没看懂），之后我会教大家如何用一种非常大略地方式来理解排列组合的递归，这也是写本文的根本目的
接下来我们看看如何用 「递归四步曲」来解排列组合,本文会从以下几个方面来讲解排列组合
什么是排列
排列的常用解法
什么是组合
组合递归解法
口试中排列组合的一些变形
什么是排列
排列的定义：从n个不同元素中，任取 m (m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，当 n = m 时，我们称这样的排列为全排列
看到这个公式，大家是不是回顾起了高中的排列公式啦
我们重新温习一下，以 1, 2, 3 这三个数字的全排列有多少种呢。
第一位我们可以选择 3 个数字，由于第二位不能与第一位相等，以是第二位只能选 2 个数字，第一，第二位既然选完了，那么第三位就只有 1 个数字可选了，以是统共有 3 x 2 x 1 = 6 种排列。
既然知道了什么是全排列，那我们来看看怎么用程序来打印全排列的所有情形：求 数字 1 到 n (n < 10) 的全排列
排列的常用解法
这道题如果暂时没什么头绪，我们看看能否用最大略的办法来实现全排列，什么是最大略的办法，暴力穷举法!
暴力穷举法
大家仔细看上文中 1，2 ，3 的全排列，便是把所有情形全部列举出来了，以是我们用暴力穷举法怎么解呢,对每一位的每种情形都遍历出来组成所有的排列，再剔除重复的排列，便是我们要的全排列了
/ 求数字第 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);}}}}}
韶光繁芜度是多少呢,做了三次循环，很显然是
很多人一看韶光繁芜度这么高，多数都会嗤之以鼻，但是要我说，得看场景，就这题来说用暴力穷举法完备没问题，n 最大才 9 啊，统共也才循环了 9^3 = 729 次,这对现在的打算机性能来说大略不值一提，就这种场景来说，其实用暴力穷举法完备可行!
这里说句题外话，我们在学习的过程中一定要视场景选择得当的技能方案，有句话说：过早的性能优化是万恶之源，说的便是这个道理，这就好比，一个初创公司，dau 不过千，却要搞分布式，中间件，一个 mysql 表，记录不过一万，却要搞分库分表。。。这就闹笑话了，记住没有最牛逼的技能，只有最得当的技能！
能办理当前实际问题的技能，便是好技能！
递归解题
这是笔者写此文的根本目的！
便是为了讲清楚怎么用递归来更好地理解排列组合！
由于我创造很多网友都以为排列组合的递归解法实在不能 Get 到点上， 当初笔者也是看了好几遍代码才勉强理解，不过过了一段韶光再看又忘了,后来根据笔者悟出的一套递归四步曲来理解，随意马虎多了，现与各位分享！
仔细看好啦
我们先来不雅观察一下规律，看下若何才能找出排列是否符合递归的条件，由于如前文 所述，必须要找出题目是否能用递归才能再用递归四步曲来解题
乍一看确实看不出什么以是然出来，那我们假设第一个数字已经选中了（假定为1），问题是不是转化为只求后面三位数的全排列了，创造没有，此时全排列从前面 n 位数的全排列转化成了求之后 n-1 位数的全排列了,问题从 n 变成了 n-1，规模变小了！
而且变小的子问题与原问题具有相同的办理思路,都是从求某位开始的全排列！
符合递归的条件！
既然我们创造排列符合递归条件，那我们就可以用递归四步曲来解了
1、定义函数的功能哀求数字 1 到 n 的全排列，我们定义以下函数的功能为求从 k 位开始的全排列,数组 arr 存的是参与全排列的 1 到 n 这些数字
public void permutation(int arr[], k) {}
2、探求递推公式把稳上面形成递归的条件：第一个数字已经选中了！
那第一位当选中有哪些情形呢,显然有以下几种情形
即在第一位上把所有的数字都选一遍，怎么做才能把所有的数字都在第一位上都选一遍呢，把第一位与其他 n-1 位数分别交流即可（把稳每一次交流前都要担保是原始顺序），如下
画外音：第一步交流自己实在便是保持不变，由于我们要担保在第一位所有数字都能取到，如果移除了这一步，则第一位少了数字 1 ，全排列就漏了
这样我们就把第一位的所有数字都选了遍，之后只要对剩余的 n-1 位数做全排列即可（即调用第一步的函数），切忌再对 n-1 再做展开,只要我们创造递推关系就行了，千万不要陷入层层展开子问题的陷阱当中去！
把稳要从函数的功能来理解，由于问题与子问题具有相同的办理思路，以是第 1 步定义的函数对子问题（求 n-1 ,n-2 ... 的全排列）同样适用!
那递归的终止条件是什么呢 ，显然是从 n 缩小到对末了一位的全排列(此时 k 指向 arr 的末了一个元素)
于是我们可以得出递推关系为:permutation(int arr[], k) = 选中第k位（将第k位与之后的 n- k 位分别交流） + permutation(int arr[], k+1)
3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中，补充后的函数如下
/ @param arr 代表全排列数字组成的数组 @param k 代表第几位/public void permutation(int[] arr, int k) {// 当 k 指向末了一个元素时,递归终止，打印此时的排列排列if (k == arr.length - 1) {System.out.println(Arrays.toString(arr));} else {for (int i = k; i < arr.length; i++) {// 将 k 与之后的元素 i 依次交流,然后可以认为选中了第 k 位swap(arr, k, i);// 第 k 位选择完成后，求剩余元素的全排列permutation(arr, k+1);// 这一步很关键：将 k 与 i 换回来，担保是初始的顺序swap(arr, k, i);}}}public static void swap (int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}
我看网上有不少人对末了一步（如图示）不理解
回过分去看上面的递归过程图中我们特意强调了把稳每一次交流时都要担保是原始顺序
以是末了一个 swap 要做的事情便是每次交流第一个数字与后面当选中的那个数，做完之后元素的全排列之后，要把数字交流回来，以担保接下来再用第一位与其他位的数字进行交流前是原始的序列，这样才能担保第一位数字与之后的 n-1 个元素依次交流之后都是不重复的。
注定一定要从函数的功能去理解递归，全排列的函数从功能上可以这么理解，选中第 k 位 + 打算之后的 n-k 位的全排序， 而且由于是递归，之后的 n-k 位也可以重复调用同样的函数持续求解！
4、求韶光/空间繁芜度由于我们只用了一个数组 arr，以是空间繁芜度显然是 O(n)，那韶光繁芜度呢，仔细看上面的编码可以很明显地看出打算 n 的全排列须要做 n 次循环，循环里是要做 2 次交流（由于是固天命字，可以认为是常数 C ），还有一次对之后 n-1 次元素的全排列以是 f(n) = n (C + f(n-1))，C是常数可以忽略,以是
f(n) = n f(n-1) = n (n-1) f(n-2) = n!,以是韶光繁芜度是 O(n!)，把稳不可能有比这个更好的韶光繁芜度了！
由于全排列的组合本身就有 n! 次，再怎么优化都肯定会有这么多次
在 n 较大的情形下显然是不可接管的，以是我们要想办法进行优化
字典序法
除了递归解法，还有一种常用的解法：字典排序法啥叫字典排序法？
举个例子：1 2 3 这三位数字的全排列如下
1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1
以上排列知足从小到大依次递增，按这种办法排列的算法就叫字典排序法。
以是我们只要从排列的最小值开始,依次按从小到大依次递增的顺序找寻下一个全排列的数字即可，直到最大值！
就能找到所有全排列。
假设我们定义了一个叫 nextPermutation 的函数,根据字典排序法，则从最小值 123 开始，持续调用这个函数即可求出所有全排列的组合,如图示
那么这个函数该怎么实现呢
有 4 个步骤
1、从右到左（从个位数往高位数）探求第一个左邻小于右邻的数，如果找不到解释此时的数字为全排列的最大值
2、再从右往左找第一个比第一步找出的数更大的数
3、交流上面两个步骤中的数
4、假设第一步探求的数对应的位置为 i，则将 i+1至末了一个元素从小到大进行排序，排好序后，此时的数字便是我们要找的那个排列
举个例子: 假设当前给的数字是 124653， 按这四个步骤来看如何探求这个数按字典排序法的下一个全排列数字
1、从右到左（从个位数往高位数）探求第一个左邻小于右邻的数，显然是 4
124653
2、再从右往左找第一个比第一步找出的数（4）更大的数, 显然是 5
124653
3、交流上面两个步骤中的数,即交流 4， 5，此时数字为 125643
4、 125643 中的 643 从小到大进行排序，显然该当为 125346,这一步的排序我们用了快排
整体思路还是很清晰的，如果不太清楚，建议大家多看几遍。
思路清楚了，代码写起来就快了，直接贴上按以上步骤来实现的代码吧，注释写得很详细了，大家可以对照着看
/ @param arr 当前排列 @return boolean 如果还有下一个全排列数，则返回 true, 否则返回 false/public booleannext_permutation(int[] arr) {int beforeIndex = 0; //记录从右到左探求第一个左邻小于右邻的数对应的索引int currentIndex;boolean isAllReverse = true; // 是否存在从右到左第一个左邻小于右邻的数对应的索引// 1. 从右到左（从个位数往高位数）探求第一个左邻小于右邻的数for(currentIndex = arr.length - 1; currentIndex > 0; --currentIndex){beforeIndex = currentIndex - 1;if(arr[beforeIndex] < arr[currentIndex]){isAllReverse = false;break;}}//如果不存在，解释这个数已经是字典排序法里的最大值，此时已经找到所有的全排列了,直接打印即可if(isAllReverse){return false;} else {// 2. 再从右往左找第一个比第一步找出的数更大的数的索引int firstLargeIndex = 0;for(firstLargeIndex = arr.length - 1; firstLargeIndex > beforeIndex; --firstLargeIndex) {if (arr[firstLargeIndex] > arr[beforeIndex]) {break;}}// 3. 交流 上述 1, 2 两个步骤中得出的两个数swap(arr, beforeIndex, firstLargeIndex);// 4. 对 beforeIndex 之后的数进行排序，这里用了快排quicksort(arr, beforeIndex + 1, arr.length);return true;}}public void swap (int[] arr, int i, int j) {int t = arr[i];arr[i] = arr[j];arr[j] = t;}
注：以上第四步的排序用到了快排（quicksort），限于篇幅关系没有贴出快排的完全代码，如果不理解快排，建议大家网上查查看，这里不做详细展开
那 next_permutation 的韶光繁芜度是多少呢，从以上的步骤中实在可以看到是第四步做快排时的韶光繁芜度，即 O(nlogn)。
next_permutation 我们写好了，接下来要探求全排列就随意马虎了，思路如下
1、 首先对参与全排列的数字数组作排序，担保初始的排列数字一定是最小的即如果起始的 int arr = {4,3,2,1} 经由快排后会变成 {1,2,3,4}
2、持续调用定义好的 next_permutation 函数，直到最大值
public void permutation(int[] arr) {// 1、 快排，担保 arr 里的元素是从小到大的quicksort(arr);// 2、持续调用定义好的 next_permutation 函数，直到最大值while(next_permutation(arr)) {System.out.println(Arrays.toString(array));}}
可以看到如果定义好了 next_permutation，在算全排列还是很大略的，那用字典序法的韶光和空间繁芜度是多少呢由于全程只用了arr 数组，空间繁芜度显示是 O(n)而韶光繁芜度显然是第一步快排的空间繁芜度 + 持续做 next_permutation 打算的韶光繁芜度。
快排的韶光繁芜度为 O(nlogn)，而 next_permutation 由于要打算 n! 次， 且根据以上剖析我们已经知道了 next_permutation 的韶光繁芜度是 O(nlogn), 以是整体的韶光繁芜度是
O(nlog) + O(n! nlogn) = O(n! nlogn)。
看起来字典序法比递归的韶光繁芜度更高,以是我们该当利用方向于利用递归吗？这里把稳: 递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数通报等，这是通过一个递归事情栈实现的。详细是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N局部变量、N形参、N调用函数地址、N返回值，这势必是影响效率的，同时，这也是内存溢出的缘故原由，由于积累了大量的中间变量无法开释。
以是在韶光繁芜度差不多的情形下，优化选择非递归的实现办法
什么是组合
看完了排列，我们来看看组合，首先我们还是先看看组合的定义
组合（combination）是一个数学名词。一样平常地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。
假设有数字1, 2, 3, 4, 要从中选择 2 个元素，共有多少种组合呢
共有 6 种
排列与组合最紧张的差异便是排列是有序的，而组合是无序的，12 和 21 对组合来说是一样的
现在我们来看看如果从 n 个元素中选出 m 的组合共有几种，之前详细地讲解了如何用递归解排列，相信大家该当对组合怎么利用递归该当有一个比较清晰的思路。
我们一起来看看，假设要从 n 选 m 的组合的解题思路
这里须要把稳的是相对付全排列的每个元素都能参与排列不同，组合中的每个元素有两种状态，选中或未选中,以是形成递归分两种情形。
如果第一个元素选中，则要从之后的 n-1 个元素中选择 m-1 个元素
如果第一个元素未当选中，则须要从之后的 n-1 个元素选择 m 个元素
递归条件既然找到了，接下来我们就按递归四步曲来解下组合。
1、定义函数的功能定义以下函数为从数组 arr 中第 k 个位置开始取 m 个元素（如下的 COMBINATION_CNT）
public static final int COMBINATION_CNT = 5; // 组合中须要当选中的个数
public static void combination(int[] arr, int k, int[] select) {
}
这里我们额外引入了一个 select 数组，这个数组里的元素如果为1，则代表相应位置的元素当选中了，如果为 0 代表未选中
如图示，以上表示 arr 的第 2，3 元素当选中作为组合
2、探求递推公式显然递推公式为
combination(arr, k,m) = (选中 k 位置的元素 +combination(arr, k+1) ) + (不选中 k 位置的元素 +combination(arr, k+1) )
那么终止条件呢，有两个
一个是当选中的元素已经即是我们要选择的组合个数了
一个是 k （开始选取的数组索引） 超出数组范围了。
3、将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中，补充后的函数如下
public static final int COMBINATION_CNT = 5; // 组合中须要当选中的个数public static void combination(int[] arr, int k, int[] select) {// 终止条件1：开始选取的数组索引 超出数组范围了if (k >= arr.length) {return;}int selectNum = selectedNum(select);// 终止条件2：选中的元素已经即是我们要选择的数组个数了if (selectNum == COMBINATION_CNT) {for (int j = 0; j < select.length; j++) {if (select[j] == 1) {System.out.print(arr[j]);}}System.out.print(\"大众\n\"大众);} else {// 第 k 位当选中select[k] = 1;combination(arr, k+1, select);// 第 k 位未当选中select[k] = 0;// 则从第 k+1 位选择 COMBINATION_CNT - selectNum 个元素combination(arr, k+1, select);}}public static void main(String[] args) {int arr = {1,2,3,4,5,6,7,8,9};int select = {0,0,0,0,0,0,0,0,0};// 一开始从 0 开始选 组合数combination(arr, 0, select);}
4、求韶光/空间繁芜度空间繁芜度：由于我们用了一个赞助数组 select, 以是空间繁芜度是 O(n)韶光繁芜度：可以看到 f(n) = 2f(n-1)，以是韶光繁芜度是O(2^n),显然是指数级别的
画外音：大家可以考虑一下怎么优化，提示:每种元素只有选中和当选中的状态，是不是对应了二进制的 0 和 1，可以考虑用位运算
口试中排列组合的一些变形
经由以上的讲解，我相信大家对排列组合的递归解法该当是很明白了，不过口试中口试官可能还会对排列组合稍加变形，以进一步稽核你的算法水平。
考虑以下情形
在全排列时参与排列的数字都是不相同的， 如果有相同的数字（比如参与排序的是 1， 1，2，3），在利用递归进行解题时，须要进行若何的改造；
在组合中 ，我们的题目是从 n 中选出 m 个数，如果要选出所有组合呢，比如给定 1，2，3，所有的组合是1, 2, 3, 12, 13, 23, 123, 此时以上的递归解法又该怎么改造。
声明：本文为作者投稿，版权归作者个人所有。
