排列组合 专题汇总
排列组合的知识在生活中无处不在，本文总结了一些高中数学中排列组合的重要知识点。此外，为了激发大家的兴趣，我在选择习题时尽可能兼具实用性和趣味性。
分步乘法原则
李健在参加《我是歌手》节目时曾被问道，7位歌手一共有多少种出场顺序。
首先，我们从第一位出场的歌手考虑，有7种可能。当第一位确定后，第二位出场的歌手就只有6种可能。当第二位确定后，第三位出场的歌手就只有5种可能......以此类推，一共有7×6×5×4×3×2×1=5040种出场顺序。
对于同一个事件，将其分为n个步骤，每个步骤分别有m1,m2,m3,...,mn种可能，那么这一事件总共就有m1×m2×m3×...×mn种可能。这就是【分步乘法原则】。
作业：1.若某手机的开机密码共有6位数，则该密码一共有多少种可能？2.六位数的正整数一共有多少个？
解答：
第一题：10^6=1000000（一百万）；
第二题：9×10×10×10×10×10=900000（九十万）。
分类加法原则
现有2只金毛，3只萨摩耶和4只阿拉斯加，任选其中一只狗作为宠物，共有多少种可能？
将本题分为三类情况，第一类情况是选金毛（2种可能），第二类情况是选萨摩耶（3种可能），第三类情况是选阿拉斯加（4种可能）。因此，共有2+3+4=9种可能。
这个解答过程看似理所当然，实际上却反映了另一个重要的基本原则，即“分类加法原则”——将同一个事件分为n类情况，每类情况分别有m1,m2,...,mn种可能，那么这一事件总共就有m1+m2+...+mn种可能。
需要强调的是：这两个原理非常重要，以下所有内容都以此为基础。
阶乘
阶乘用数学符号“!”（感叹号）表示。规定0!=1，对于正整数n，n!=1×2×3×...×n。
排列数与组合数
排列数用字母A（Arrangement）和两个角标表示，读作“A,n,m”（详见下图）。规定n为正整数，m为自然数，且n≥m。由于不方便输入角标，以下我就用A(n,m)表示。
排列数
它的含义是指：在n个【互不相同的】元素中，任取其中m个元素【有顺序地】进行排列。
比如，第一期中的问题“7位歌手总共有多少种出场顺序”，就可以表示为A(7,7)=7!=5040。现在将本题稍微变化一下：7位歌手只需要其中任意6位出场（有1位歌手不用出场），总共有多少种顺序？这时就可以表示为A(7,6)=5040。
作业：1.若某手机的开机密码共有6位各不相同的数，则该密码一共有多少种可能？
2.每位数各不相同的六位数共有多少个？
解答：
第一题：A(10,6)=151200；
第二题：9×9×8×7×6×5=136080。
组合数用字母C（Combination）和两个角标表示，读作“C,n,m”（详见下图）。规定n为正整数，m为自然数，且n≥m。由于不方便输入角标，以下我就用C(n,m)表示。
排列数
它的含义是指在n个【互不相同的】元素中，任取其中m个元素【无顺序地】进行组合。
作业：某女生寝室共有6人，假设她们中至少3人才能创建一个QQ群，问该寝室最多会有几个QQ群？（提示：要用分类加法原则）
解答：C(6,3)+C(6,4)+C(6,5)+C(6,6)=20+15+6+1=42。
请大家多多留意本题！下面我会用【二项式定理】再给出一种的解法。
消序法
在排列数和组合数的定义中，我强调了是“n个互不相同的元素”。但实际应用中经常会出现含有相同元素的情况，这时就要用【消序法】。
比如，b、e、e三个字母共有几种排序？
首先，将b、e、e看作是3个不同的元素，就有A(3,3)=6种排序。由于我们假设了两个e是不同的元素，因此将它们两进行排序，就有A(2,2)=2种可能。最后，设实际的排序共有x种可能，根据分步乘法原则，2x=6，即x=3。这3种排序分别是bee、ebe和eeb。
因为两个e是完全相同的元素，所以排序时显然不能直接用A(3,3)，而必须通过上述的【消序法】修改计算公式，才能得到正确的结果。
作业：afternoon这9个字母共有几种排序？
解答：A(9,9)÷[A(2,2)×A(2,2)]=90720。
练习巩固
1.英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对4道题的概率是多少？
2.英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对前4道题的概率是多少？
3.英语考试中某道多选题共有4个选项，请问蒙对该题的概率是多少？.
4.英语考试中某排序题共有5题，但选项共有7个，请问全蒙对的概率是多少？
解答：
第一题：首先，蒙对一道题的概率为1/4，蒙错一道题的概率为3/4。在这5道题中任选其中4道，共有C(5,4)=5种情况，因此答案为5×(1/4)×(1/4)×(1/4)×(1/4)×(3/4)=15/1024。
第二题：它与第一题的不同之处在于——要求蒙对的是前4道题。也就是说，问题给定了具体的元素，不需要再在这5道题中进行选择了。答案为(1/4)×(1/4)×(1/4)×(1/4)×(3/4)=3/1024。
第三题：与女生寝室那道题相似。分为3类情况——正确答案有2个选项；有3个选项；有4个选项。因此，总共有C(4,2)+C(4,3)+C(4,4)=6+4+1=11种组合，答案为1/11。
第四题：共有A(7,5)=2520种排序，答案为1/2520。
二项式定理与杨辉三角
首先，我们来研究一下如何计算(a+b)²的展开式。
第一步，让两个(a+b)的a相乘，共有C(2,2)=1种组合，得a²。第二步，让其中一个(a+b)的a与另一个(a+b)的b相乘，这时对a就有C(2,1)=2种选择。并且一旦选定了某个a，另一个b也就确定了，因此共有2种选择，得2ab。最后，让两个(a+b)的b相乘，也有C(2,2)=1种组合，得b²。综上，(a+b)²=a²+2ab+b²。
同理，可以计算出(a+b)³的展开式，详见下图。
以此类推，可得(a+b)∧n(n为正整数)的展开式，这就是【二项式定理】。
从n=0开始，依次将二项式定理中的所有系数列出，就可以得到【杨辉三角】。
它最早由我国的北宋数学家贾宪（生卒年不详）发现，后来被南宋数学家杨辉（生卒年不详）引用，并流传至今。在欧洲，它最早由法国科学家帕斯卡（1623-1662，同时也是压强的单位）发现，但比我国晚了数百年。
令a=b=1，可得一个重要公式，详见下图。
因此，对于这道习题：某女生寝室共有6人，假设她们中至少3人才能建一个QQ群，问这个寝室最多能有几个QQ群？就有一个更快捷的计算方法！
解答：C(6,3)+C(6,4)+C(6,5)+C(6,6)=2∧6-C(6,0)-C(6,1)-C(6,2)=64-1-6-15=42。
二项分布与超几何分布
本节将简要介绍排列组合在概率统计中的应用。
我们来回顾一下这道习题：英语考试中某阅读题共有5道单选题（每题4个选项），请问恰好蒙对4道的概率是多少？
我们有理由将“蒙5道题”看作“5次独立重复的试验”。因为每蒙一道题对蒙对（或蒙错）下一题的概率没有任何影响，所以这5次重复试验是相互独立的。这样的过程就是【独立重复试验】。
类似地，对于抛n次硬币，因为每抛一次硬币对下一次抛硬币是正面（或反面）的概率没有任何影响，所以抛n次硬币就是n次独立重复试验。
如果随机变量X表示n次独立重复试验中某事件(比如蒙对一道题、硬币反面向上)发生的次数，那么X服从【二项分布】。
现有5个白球和5个红球在黑箱中，不放回地依次抽取。不难发现，第一次抽到红球的概率和第二次抽到红球的概率就不一样，这不再是独立重复试验。此时，随机变量X就服从【超几何分布】。
一文学会排列组合 排列组合公式
排列组合公式 一文学会排列组合确实，相信很多人 包括我自己都有类似的感慨，对某个知识点，看确实是看懂了，但如果真的再用同样的套路再去解一些带有同样解题思路，但稍加变形的题，往往会束手无策。对这种情况有啥好的解决办法吗？
排列组合公式 一文学会排列组合
除了勤加练习，还有一良策！
鲁迅先生说：如果学习算法，最好一段时间内只刷某种算法思想或某种数据结构的题，啥意思呢?比如说你上次学了递归，那就持续找递归的题来刷，学了链表，这段时间就专门刷链表的题，千万不可今天刷递归，明天刷动态规划，后天又开始学习贪心算法。。。新手最怕的就是以为自己懂了，浅尝辄止，这是新手的大忌！一定要对同一类型的题穷追猛打，形成肌肉记忆，这样之后再碰到同一类型的题就会条件反射地一看:哦,这题用 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 n10 的全排列
排列的常用解法
这道题如果暂时没什么头绪，我们看看能否用最简单的方式来实现全排列，什么是最简单的方式，暴力穷举法!
暴力穷举法
大家仔细看上文中 1，2 ，3 的全排列，就是把所有情况全部列举出来了，所以我们用暴力穷举法怎么解呢,对每一位的每种情况都遍历出来组成所有的排列，再剔除重复的排列，就是我们要的全排列了
/**
* 求数字第 1 到 n 的全排列
*/
public void permutation int n {
for int i = 1; in + 1; i ++ {
for int j = 1; jn + 1; j ++ {
for int k = 1; kn + 1; k ++ {
if i != ji != kj != k {
System.out.println i + j + k;
}}}}}
时间复杂度是多少呢,做了三次循环，很显然是
很多人一看时间复杂度这么高，多数都会嗤之以鼻，但是要我说，得看场景，就这题来说用暴力穷举法完全没问题，n 最大才 9 啊，总共也才循环了 9^3 = 729 次,这对现在的计算机性能来说简单不值一提，就这种场景来说，其实用暴力穷举法完全可行!
这里说句题外话，我们在学习的过程中一定要视场景选择合适的技术方案，有句话说：过早的性能优化是万恶之源，说的就是这个道理，这就好比，一个初创公司，dau 不过千，却要搞分布式，中间件，一个 mysql 表，记录不过一万，却要搞分库分表。。。这就闹笑话了，记住没有最牛逼的技术，只有最合适的技术！能解决当前实际问题的技术，就是好技术！
递归解题
这是笔者写此文的根本目的！就是为了讲清楚怎么用递归来更好地理解排列组合！因为我发现很多网友都觉得排列组合的递归解法实在不能 Get 到点上， 当初笔者也是看了好几遍代码才勉强理解，不过过了一段时间再看又忘了,后来根据笔者悟出的一套递归四步曲来理解，容易多了，现与各位分享！仔细看好啦
我们先来观察一下规律，看下怎样才能找出排列是否符合递归的条件，因为如前文 所述，必须要找出题目是否能用递归才能再用递归四步曲来解题
一文学会排列组合
乍一看确实看不出什么所以然出来，那我们假设第一个数字已经选中了 假定为1，问题是不是转化为只求后面三位数的全排列了，发现没有，此时全排列从前面 n 位数的全排列转化成了求之后 n-1 位数的全排列了,问题从 n 变成了 n-1，规模变小了！而且变小的子问题与原问题具有相同的解决思路,都是从求某位开始的全排列！符合递归的条件！
既然我们发现排列符合递归条件，那我们就可以用递归四步曲来解了
定义函数的功能要求数字 1 到 n 的全排列，我们定义以下函数的功能为求从 k 位开始的全排列,数组 arr 存的是参与全排列的 1 到 n 这些数字
public void permutation int arr[], k {
}
寻找递推公式注意上面形成递归的条件：第一个数字已经选中了！那第一位被选中有哪些情况呢,显然有以下几种情况
即在第一位上把所有的数字都选一遍，怎么做才能把所有的数字都在第一位上都选一遍呢，把第一位与其他 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
将第二步的递推公式用代码表示出来补充到步骤 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; iarr.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 位也可以重复调用同样的函数持续求解！
求时间/空间复杂度由于我们只用了一个数组 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 个步骤
从右到左 从个位数往高位数寻找第一个左邻小于右邻的数，如果找不到说明此时的数字为全排列的最大值
再从右往左找第一个比第一步找出的数更大的数
交换上面两个步骤中的数
假设第一步寻找的数对应的位置为 i，则将 i+1至最后一个元素从小到大进行排序，排好序后，此时的数字就是我们要找的那个排列
举个例子: 假设当前给的数字是 124653， 按这四个步骤来看如何寻找这个数按字典排序法的下一个全排列数字
从右到左 从个位数往高位数寻找第一个左邻小于右邻的数，显然是 4
124653
再从右往左找第一个比第一步找出的数 4更大的数, 显然是 5
124653
交换上面两个步骤中的数,即交换 4， 5，此时数字为 125643
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; currentIndex0; --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; firstLargeIndexbeforeIndex; --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 我们写好了，接下来要寻找全排列就容易了，思路如下
首先对参与全排列的数字数组作排序，保证初始的排列数字一定是最小的即如果起始的 int arr = {4,3,2,1} 经过快排后会变成 {1,2,3,4}
持续调用定义好的 next_permutation 函数，直到最大值
public void permutation int[] arr {
// 快排，保证 arr 里的元素是从小到大的
quicksort arr;
// 持续调用定义好的 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 个元素
一文学会排列组合
递归条件既然找到了，接下来我们就按递归四步曲来解下组合。
定义函数的功能定义以下函数为从数组 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 元素被选中作为组合
寻找递推公式显然递推公式为
combination arr, k,m = 选中 k 位置的元素 +combination arr, k+1 + 不选中 k 位置的元素 +combination arr, k+1
那么终止条件呢，有两个
一个是被选中的元素已经等于我们要选择的组合个数了
一个是 k 开始选取的数组索引 超出数组范围了。
将第二步的递推公式用代码表示出来补充到步骤 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; jselect.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;
}
求时间/空间复杂度空间复杂度：由于我们用了一个辅助数组 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, 此时以上的递归解法又该怎么改造。
|排列组合、专题汇总
一文学会排列组合 专题汇总 排列组合 排列组合公式