1.排列组合问题

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

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

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

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

2.所有子集

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

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

import org.apache.commons.lang3.StringUtils; import java.util.ArrayList; public class SubSet { public static int[] nums = {1, 2, 3}; public static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public static void subset(ArrayList<Integer> inner, int start) { for(int i=start; i<nums.length; i++) { inner.add(nums[i]); result.add(new ArrayList<>(inner)); subset(inner, i+1); inner.remove(inner.size()-1); } } public static void main(String[] args) { ArrayList<Integer> inner = new ArrayList<>(); result.add(inner); subset(inner, 0); for(ArrayList<Integer> each: result) { System.out.println(StringUtils.join(each, ",")); } } } 

上面代码的输出为

讯享网 1 1,2 1,2,3 1,3 2 2,3 3 

刚好8种情况，而且看输出结果，符合我们的预期。

上面的分析过程，实际上就是代码中函数不停压栈然后回溯调用的过程。建议同学们可以实际debug一下，看一看代码运行过程，会理解得更加深刻。

3.从n个元素中选择k个组合

第二部分是求所有的子集，如果我们限定子集元素的个数，即从n个元素中选择k个元素组合，就是常见的$C(n,k)$问题。

解法思路基本与上面相同，先看代码。

import org.apache.commons.lang3.StringUtils; import java.util.ArrayList; public class SelectK { public static int[] nums = {1, 2, 3}; public static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public static void select(ArrayList<Integer> inner, int start, int k) { for(int i=start; i<nums.length; i++) { inner.add(nums[i]); if (inner.size() == k) { result.add(new ArrayList<>(inner)); inner.remove(inner.size()-1); continue; } select(inner, i+1, k); inner.remove(inner.size()-1); } } public static void main(String[] args) { ArrayList<Integer> inner = new ArrayList<>(); int k = 2; select(inner, 0, k); for(ArrayList<Integer> each: result) { System.out.println(StringUtils.join(each, ",")); } } } 

结果为：

讯享网

讯享网1,2 1,3 2,3 

与求所有子集不一样的地方在于，只有当inner中的元素个数为k时，才将inner添加到result中。同时，添加完毕以后，先将最后一个元素删除，然后就可以直接continue，结束本次循环。

4.n个元素的全排列

按照我们之前的分析，n个不重复的元素，全排列的情况总共为$n!$种。假设数组{1, 2, 3}，那么全排列一共有6种情况。

还是先上代码

import org.apache.commons.lang3.StringUtils; import java.util.ArrayList; public class PermutationN { public static int[] nums = {1, 2, 3}; public static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public static void permuation(ArrayList<Integer> inner) { if (inner.size() == nums.length) { result.add(new ArrayList<>(inner)); return; } for(int i=0; i<nums.length; i++) { if (inner.contains(nums[i])) { continue; } inner.add(nums[i]); permuation(inner); inner.remove(inner.size()-1); } } public static void main(String[] args) { ArrayList<Integer> inner = new ArrayList<>(); permuation(inner); for(ArrayList<Integer> each: result) { System.out.println(StringUtils.join(each, ",")); } } } 

同样来分析一下代码的思路：
1.如果inner的size满足条件，加入到result中，并返回。
2.从第一个元素开始循环：
2.1 如果该元素在inner中，表示该元素已经被访问，本次循环continue。
2.2 如果元素不在inner中，加入inner。
2.3 递归调用permuation方法。
2.4 本次permuation方法调用结束以后，删除掉inner中的最后一个元素。

思路是不是还算比较清晰。同样的，如果看上去有点晕，也建议大家去IDE中debug，观察一下函数递归调用的整个流程。

inner.contains(nums[i]) 这一行起的作用，是判断该元素有没有被访问，实际中更常见的另外一种写法是用一个visit数组来记录元素被访问的情况，下面我们采用visit数组的写法来表示一下。

讯享网import org.apache.commons.lang3.StringUtils; import java.util.ArrayList; public class PermutationN { public static int[] nums = {1, 2, 3}; public static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public static boolean[] visit = new boolean[nums.length]; public static void permuation(ArrayList<Integer> inner, boolean[] visit) { if (inner.size() == nums.length) { result.add(new ArrayList<>(inner)); return; } for(int i=0; i<nums.length; i++) { if (visit[i]) { continue; } visit[i] = true; inner.add(nums[i]); permuation(inner, visit); inner.remove(inner.size()-1); visit[i] = false; } } public static void main(String[] args) { ArrayList<Integer> inner = new ArrayList<>(); permuation(inner, visit); for(ArrayList<Integer> each: result) { System.out.println(StringUtils.join(each, ",")); } } } 

用visit数组标记该元素是否被访问，与之前的版本相比，多了两个步骤：
1.该元素被访问，visit数组该位置被置为true;
2.递归回溯的时候，visit数组该位置被置为false。

5.n个有重复元素的全排列

import org.apache.commons.lang3.StringUtils; import java.util.ArrayList; import java.util.Arrays; public class PermutationDuplicate { public static int[] nums = {1, 2, 1}; public static ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public static boolean[] visit = new boolean[nums.length]; public static void permuation(ArrayList<Integer> inner, boolean[] visit) { if (inner.size() == nums.length) { result.add(new ArrayList<>(inner)); return; } for(int i=0; i<nums.length; i++) { if (visit[i]) { continue; } if (i > 0 && nums[i] == nums[i-1] && !visit[i-1]) { continue; } inner.add(nums[i]); visit[i] = true; permuation(inner, visit); inner.remove(inner.size()-1); visit[i] = false; } } public static void main(String[] args) { Arrays.sort(nums); ArrayList<Integer> inner = new ArrayList<>(); permuation(inner, visit); for(ArrayList<Integer> each: result) { System.out.println(StringUtils.join(each, ",")); } } } 

重点看与上面不同的地方：
1.要先对数组进行排序，保证有序。
2.

讯享网 if (i > 0 && nums[i] == nums[i-1] && !visit[i-1]) { continue; } 

6.套路总结

上面各个case挨个解完以后，下面我们来总结一下排列组合问题的套路。

先看排列问题：

result = [] def permutation(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 permutation(路径, 选择列表) 撤销选择 

再看看组合问题

讯享网result = [] def permutation(路径, 选择列表): for 选择 in 选择列表: 做选择 permutation(路径, 选择列表) 撤销选择 

组合的套路，本质也是回溯法的使用。与排列稍微不一样的地方在于，组合问题的结束条件可以不用写出来，等循环结果即可。