最全排列组合算法详解以及套路总结一文突破

项目github地址：bitcarmanlee easy-algorithm-interview-and-practice 经常有同学私信或留言询问相关问题，V号bitcarmanlee。github上star的同学，在我能力与时间允许范围内，尽可能帮大家解答相关问题，一起进步。

排列组合是经典的算法问题，相关的内容中学阶段就学习过。在讲算法实现之前，我们先简单复习一下排列组合的相关定义。 排列，英文名称为Permutation，简称P。假设有一个数组{1, 2, 3, 4, 5}，我们需要将数组中的所有元素进行排序，那么第一个位置，我们可以选择五个数字的任何一个，共有5种选择。第二个位置，可以选择剩余四个数字的任何一个，共有4种选择。第三个位置，可以选择剩余三个数字中的任何一个，共有3种选择。第四个位置，可以选择剩余两个数字中的任何一个，共有2种选择。最后一个位置，因为只剩一个数字，没得选择，所有只有一种选择。那么该数组总共的排列个数为 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1 = 120 5*4*3*2*1=120 5∗4∗3∗2∗1=120种。 如果数组的元素不重复，元素个数为N，按照上面的推导，容易得出该数组的全排列个数为 N ! N! N!，即 P ( N ) = N ! P(N) = N! P(N)=N!

很多时候我们不做全排列，比如5个元素，我们只需要取3个进行排序，按照前面的分析，很容易得知排列的个数为 5 ∗ 4 ∗ 3 = 60 5*4*3=60 5∗4∗3=60种，后面的 2 ∗ 1 2*1 2∗1两种情况被舍弃掉了。因此，从N个元素中选择k个做排列，公式也很容易写出来: P ( N , k ) = N ! ( N − k ) ! P(N, k) = \frac{N!}{(N-k)!} P(N,k)=(N−k)!N!​

组合，英文名为Combination，简称C。假设同样是数组{1, 2, 3, 4, 5}，我们需要从数组中选择任意3个元素，那么有多少种方式呢？ 根据前面的推导，我们能够得知，如果从5个元素中选择3个元素，排列的方式有 P ( 5 , 3 ) = 5 ! ( 5 − 3 ) ! = 60 P(5, 3) = \frac{5!}{(5-3)!} = 60 P(5,3)=(5−3)!5!​=60种。但是组合的时候，对顺序是不敏感的，比如我们选1,2,3与选1,3,2，虽然是两种排列方式，但是在组合里是一种情况。3个元素的全排列一共有 3 ! = 6 3!=6 3!=6种，所以组合的公式为 C ( N , K ) = N ! ( N − k ) ! k ! C(N,K) =\frac{N!}{(N-k)!k!} C(N,K)=(N−k)!k!N!​

同时有二项式定理: C ( n , 0 ) + C ( n , 1 ) + C ( n , 2 ) + ⋯ + C ( n , n ) = 2 n C(n, 0) + C(n, 1) + C(n, 2) + \cdots + C(n, n) = 2^n C(n,0)+C(n,1)+C(n,2)+⋯+C(n,n)=2n

首先我们看看求所有子集的情况：假设现在数组有三个不重复的元素{1, 2, 3}，求该数组所有的子集。 根据二项式定理，我们不难得出该数组所有的子集个数为 C ( 3 , 0 ) + C ( 3 , 1 ) + C ( 3 , 2 ) + C ( 3 , 3 ) = 2 3 = 8 C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3) = 2^3 = 8 C(3,0)+C(3,1)+C(3,2)+C(3,3)=23=8

二话不说，先上代码，后面再分析具体思路。