假设有数字1，2，3，4。有多少种组合可供选择两种元素？
有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；//要在组合中选择的数字
公共静态void组合(int[] arr，int k，int[] select) {
}
这里我们引入一个额外的选择数组。如果该数组中的元素为1，则表示选择了相应位置的元素，如果为0，则表示没有选择。
如图所示，选择上面arr的第2和第3个元素作为组合。
2.寻找递推公式。显然，递归公式是
组合(arr，k，m) =(检查k位置的元素+组合(arr，k+1))+(取消检查k位置的元素+组合(arr，k+1))
终止条件呢？有两个
一个是选择的元素已经等于我们想要选择的组合数。
一种是K(开头选择的数组索引)超出数组范围。
3.步骤2的递归公式用代码表示，并添加到步骤1中定义的函数中。增加的功能如下
public static final int COMBINATION_CNT = 5; // 组合中需要被选中的个数public static void combination(int[] arr, int k, int[] select) {// 终止条件1：开始选取的数组索引 超出数组范围了if (k gt;= arr.length) {return;}int selectNum = selectedNum(select);// 终止条件2：选中的元素已经等于我们要选择的数组个数了if (selectNum == COMBINATION_CNT) {for (int j = 0; j lt; 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。此时应该如何修改上面的递归解法？
声明:本文为作者投稿，版权归作者个人所有。
