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

1.排列组合问题

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

2.所有子集

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

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

思路是不是还算比较清晰。同样的，如果看上去有点晕，也建议大家去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 
  
    > result = new ArrayList<>(); public static boolean[] visit = new boolean[nums.length]; public static void permuation(ArrayList 
   
     inner, boolean[] visit) { if (inner.size() == nums.length) { result.add(new ArrayList<>(inner)); return; } for(int i=0; i 
    
      inner = new ArrayList<>(); permuation(inner, visit); for(ArrayList 
     
       each: result) { System.out.println(StringUtils.join(each, ",")); } } } 
      
     
    
  

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 
  
    > result = new ArrayList<>(); public static boolean[] visit = new boolean[nums.length]; public static void permuation(ArrayList 
   
     inner, boolean[] visit) { if (inner.size() == nums.length) { result.add(new ArrayList<>(inner)); return; } for(int i=0; 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 
     
       inner = new ArrayList<>(); permuation(inner, visit); for(ArrayList 
      
        each: result) { System.out.println(StringUtils.join(each, ",")); } } } 
       
      
     
    
  

 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(路径, 选择列表) 撤销选择 

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