关于算法:一文拿捏全排列组合子集问题

3次阅读

共计 8287 个字符，预计需要花费 21 分钟才能阅读完成。

Hello，大家好，我是 bigsai，long time no see！在刷题和面试过程中，咱们常常遇到一些排列组合类的问题，而全排列、组合、子集等问题更是十分经典问题。本篇文章就带你彻底搞懂全排列！

求全排列？

全排列即：n 个元素取 n 个元素 (所有元素) 的所有 排列组合状况。

求组合？

组合即：n 个元素取 m 个元素的所有 组合状况(非排列)。

求子集？

子集即：n 个元素的所有子集 ( 所有可能的组合状况)。

总的来说全排列数值个数是所有元素，不同的是排列程序；而组合是选取固定个数的组合状况(不看排列)；子集是对组合拓展，所有可能的组合状况(同不思考排列)。

当然，这三种问题，有相似之处又略有所不同，咱们接触到的全排列可能更多，所以你能够把组合和子集问题认为是全排列的拓展变形。且问题可能会遇到 待处理字符是否有反复 的状况。采取不同的策略去去重也是相当要害和重要的！在各个问题的具体求解上办法可能不少，在全排列上最风行的就是 邻里调换法 和回溯法 ，而其余的组合和子集问题是经典回溯问题。而本篇最重要和根底的就是要把握这两种办法实现的 无反复全排列，其余的都是基于这个进行变换和拓展。

全排列，元素总数为最大，不同是 排列的程序。

这个问题刚好在力扣 46 题是原题的，大家学完能够去 a 试试。

问题形容：

给定一个 没有反复 数字的序列，返回其所有可能的全排列。

示例：

输出: [1,2,3]
输入:
[[1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

回溯法实现无反复全排列

回溯算法用来解决搜寻问题，而全排列刚好也是一种搜寻问题，先回顾一下什么是回溯算法：

回溯算法实际上一个相似枚举的搜寻尝试过程，次要是在搜寻尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的门路.

而全排列刚好能够应用试探的办法去枚举所有中可能性。一个长度为 n 的序列或者汇合。它的所有排列组合的可能性共有 n！ 种。具体的试探策略如下：

从待选汇合中选取第一个元素(共有 n 种状况)，并标记该元素曾经被应用不能再应用。
在步骤 1 的根底上进行递归到下一层，从残余 n - 1 个元素中依照 1 的办法找到一个元素并标记，持续向下递归。
当所有元素被标记后，程序收集被标记的元素存储到后果中，以后层递归完结，回到上一层(同时将以后层标记的元素革除标记)。这样始终执行到最初。

回溯的流程如果从伪代码流程大抵为这样：

递归函数：如果汇合所有元素被标记：将长期贮存增加到后果集中
  否则：从汇合中未标记的元素中选取一个存储到长期汇合中
      标记该元素被应用
      下一层递归函数
      (这层递归完结)标记该元素未被应用

如果用序列 1 2 3 4来示意这么回溯的一个过程，能够用这张图来显示：

用代码来实现思路也是比拟多的，须要一个 List 去存储长期后果是很有必要的，然而对于原汇合咱们标记也有两种解决思路，第一种是应用 List 存储汇合，应用过就移除而后递归下一层，递归结束后再增加到原来地位。另一种思路就是应用固定数组存储，应用过对应地位应用一个 boolean 数组对应地位标记一下，递归完结后再还原。因为 List 频繁查找插入删除效率个别比拟低，所以咱们个别 应用一个 boolean 数组去标记该地位元素是否被应用。

具体实现的代码为：

List<List<Integer>> list;
public List<List<Integer>> permuteUnique(int[] nums) {list=new ArrayList<List<Integer>>();// 最终的后果
    List<Integer> team=new ArrayList<Integer>();// 回溯过程收集元素
    boolean jud[]=new boolean[nums.length];// 用来标记
    dfs(jud, nums, team, 0);
    return list;
}
private  void dfs(boolean[] jud, int[] nums, List<Integer> team, int index) {
    int len = nums.length;
    if (index == len)// 进行
    {list.add(new ArrayList<Integer>(team));
    } else
        for (int i = 0; i < len; i++) {if (jud[i]) // 以后数字被用过 以后即不可用
                continue;
            team.add(nums[i]);
            jud[i]=true;// 标记该元素被应用
            dfs(jud, nums, team, index + 1);
            jud[i] = false;// 还原
            team.remove(index);// 将后果移除长期汇合
        }
}

批改一下输入的后果和下面思维导图也是统一的：

邻里调换法实现无反复全排列

回溯的测试是试探性填充，是对每个地位进行独自思考赋值。而邻里调换的办法尽管是也是递归实现的，然而他是一种基于替换的策略和思路。而了解起来也是非常简单，邻里调换的思路是从左向右进行思考。

因为序列是没有反复的，咱们开始将数组分成两个局部：临时确定局部 和未确定局部 。开始的时候均是未确定局部，咱们须要妥善处理的就是未确定局部。在未确定局部的序列中，咱们须要让前面未确定的每一位都有机会处在未确定的首位，所以未确定局部的第一个元素就要和 每一个顺次进行替换 (包含本人)，替换实现之后再向下进行递归求解其余的可能性，求解结束之后要替换回来(还原) 再和前面的进行替换。这样当递归进行到最初一层的时候就将数组的值增加到后果集中。如果不了解能够参考下图进行了解：

实现代码为：

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>>list=new ArrayList<List<Integer>>();
        arrange(nums,0,nums.length-1,list);
        return list;
     }

    private void arrange(int[] nums, int start, int end, List<List<Integer>> list) {if(start==end)// 到最初一个 增加到后果中
          {List<Integer>list2=new ArrayList<Integer>();
              for(int a:nums)
              {list2.add(a);
              }
              list.add(list2);
          }
          for(int i=start;i<=end;i++)// 未确定局部开始替换
          {swap(nums,i,start);
              arrange(nums, start+1, end, list);
              swap(nums, i, start);// 还原
          }
        
    }
    private void swap(int[] nums, int i, int j) {int team=nums[i];
        nums[i]=nums[j];
        nums[j]=team;
    }
}

那么邻里调换和回溯求解的全排列有什么区别呢? 首先回溯法求得的全排列如果这个序列有序失去的后果是字典序的，因为其策略是填充，先小后大有序，而邻里调换没有这个特色。其次邻里调换在这种状况下的效率要高于回溯算法的，尽管量级差不多然而回溯算法须要保护一个汇合频繁增删等占用肯定的资源。

有反复对应的是力扣第 47 题，题目形容为：

给定一个可蕴含反复数字的序列 nums，按任意程序 返回所有不反复的全排列。

示例 1：

输出：nums = [1,1,2]
输入：[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输出：nums = [1,2,3]
输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提醒：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

这个和下面不反复的全排列略有不同，这个输出数组中可能蕴含反复的序列，咱们怎么样采取适合的策略去反复才是至关重要的。咱们同样针对回溯和邻里调换两种办法进行剖析。

回溯剪枝法
因为回溯残缺的比间接递归慢，所以刚开始并没有思考应用回溯算法，然而这里用回溯剪枝相比递归邻里调换办法更好一些，对于不应用哈希去重的办法，首先进行排序预处理是没有悬念的，而回溯法去重的要害就是防止雷同的数字因为绝对秩序问题造成反复，所以在这里雷同数字在应用上 绝对地位必须不变，而具体剪枝条的规定如下：

先对序列进行排序
试探性将数据放到以后地位
- 如果以后地位数字曾经被应用，那么不可应用
- 如果以后数字和前一个相等然而前一个没有被应用，那么以后不能应用，须要应用前一个数字。

思路很简略，实现起来也很简略：

List<List<Integer>> list;
public List<List<Integer>> permuteUnique(int[] nums) {list=new ArrayList<List<Integer>>();
    List<Integer> team=new ArrayList<Integer>();
    boolean jud[]=new boolean[nums.length];
    Arrays.sort(nums);
    dfs(jud, nums, team, 0);
    return list;
}
private  void dfs(boolean[] jud, int[] nums, List<Integer> team, int index) {
    // TODO Auto-generated method stub
    int len = nums.length;
    if (index == len)// 进行
    {list.add(new ArrayList<Integer>(team));
    } else
        for (int i = 0; i < len; i++) {if (jud[i]||(i>0&&nums[i]==nums[i-1]&&!jud[i-1])) // 以后数字被用过 或者前一个相等的还没用，以后即不可用
                continue;
              team.add(nums[i]);
              jud[i]=true;
              dfs(jud, nums, team, index + 1);
            jud[i] = false;// 还原
            team.remove(index);
        }
}

邻里调换法

咱们在执行递归全排列的时候，次要考的是要把反复的状况搞上来，邻里调换又要怎么去重呢？

应用 HashSet 这种形式这里就不探讨啦，咱们在进行替换 swap 的时候从前往后，后面的确定之后就不会在动，所以咱们要 慎重考虑和谁替换 。比方 1 1 2 3 第一个数 有三种状况而不是四种状况(两个 1 1 2 3 为一个后果)：

1 1 2 3 // 0 0 地位替换
2 1 1 3 // 0 2 地位替换
3 1 2 1 // 0 3 地位替换

另外比方 3 1 1 序列,3 和本人替换，和前面两个 1 只能和其中一个进行替换，咱们这里能够约定和第一个呈现的进行替换，咱们看一个图解局部过程：

所以，当咱们从一个 index 开始的时候要记住以下的规定：同一个数只替换一次(包含值等于本人的数)。在判断前面值是否呈现的时候，你能够遍历，也能够应用 hashSet(). 当然这种办法的痛点就是判断前面呈现的数字效率较低。所以在可能反复的状况这种办法效率一般般。

具体实现的代码为：

public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> list=new ArrayList<List<Integer>>();
         arrange(nums, 0, nums.length-1, list);
         return list;
     }

private void arrange(int[] nums, int start, int end, List<List<Integer>> list) {if(start==end)
      {List<Integer>list2=new ArrayList<Integer>();
          for(int a:nums)
          {list2.add(a);
          }
          list.add(list2);
      }
      Set<Integer>set=new HashSet<Integer>();      
      for(int i=start;i<=end;i++)
      {if(set.contains(nums[i]))
              continue;
             set.add(nums[i]);             
          swap(nums,i,start);
          arrange(nums, start+1, end, list);
          swap(nums, i, start);
      }    
}
private void swap(int[] nums, int i, int j) {int team=nums[i];
    nums[i]=nums[j];
    nums[j]=team;
}

组合问题能够认为是全排列的变种，问题形容（力扣 77 题）:

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输出: n = 4, k = 2
输入:
[[2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

剖析：

这个问题经典回溯问题。组合须要记住只看元素而不看元素的程序，比方 a b 和b a 是同一个组合。要 防止这样的反复是外围，而防止这样的反复，须要借助一个 int 类型保留以后抉择元素的地位，下次只能遍历选取下标地位前面的数字，而 k 个数，能够通过一个数字类型来记录回溯到以后层解决数字的个数来管制。

具体实现也很容易，须要创立一个数组贮存对应数字，用 boolean 数组判断对应地位数字是否应用，这里就不必 List 存储数字了，最初通过判断 boolean 数组将数值增加到后果中也是可行的。实现代码为：

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> valueList=new ArrayList<List<Integer>>();// 后果
        int num[]=new int[n];// 数组存储 1 -n
        boolean jud[]=new boolean[n];// 用于判断是否应用
        for(int i=0;i<n;i++)
        {num[i]=i+1;
        }
    
        List<Integer>team=new ArrayList<Integer>();
        dfs(num,-1,k,valueList,jud,n);
        return valueList;
    }
    private void dfs(int[] num,int index, int count,List<List<Integer>> valueList,boolean jud[],int n) {if(count==0)// k 个元素满
        {List<Integer>list=new ArrayList<Integer>();
            for(int i=0;i<n;i++)
            {if (jud[i]) {list.add(i+1);
                }
            }
            valueList.add(list);
        }
        else {for(int i=index+1;i<n;i++)// 只能在 index 后遍历 回溯向下
            {jud[i]=true;
                dfs(num, i, count-1, valueList,jud,n);
                jud[i]=false;// 还原
            
            }
        }    
    }
}

子集问题和组合有些类似。这里解说数组中无反复和有反复的两种状况。

问题形容(力扣 78 题)：

给你一个整数数组 nums，数组中的元素互不雷同。返回该数组所有可能的子集（幂集）。

解集不能蕴含反复的子集。你能够按任意程序返回解集。

示例 1：

输出：nums = [1,2,3]
输入：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输出：nums = [0]
输入：[[],[0]]

提醒：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素互不雷同

子集和下面的组合有些类似，当然咱们不须要判断有多少个，只须要依照组合回溯的策略 递归进行到最初 ， 每进行的一次递归函数都是一种状况都要退出到后果中(因为采取的策略不会有反复的状况)。

实现的代码为：

class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> valueList=new ArrayList<List<Integer>>();
        boolean jud[]=new boolean[nums.length];
        List<Integer>team=new ArrayList<Integer>();
        dfs(nums,-1,valueList,jud);
        return valueList;
    }
    private void dfs(int[] num,int index,List<List<Integer>> valueList,boolean jud[]) {
        {// 每进行递归函数都要退出到后果中
            List<Integer>list=new ArrayList<Integer>();
            for(int i=0;i<num.length;i++)
            {if (jud[i]) {list.add(num[i]);
                }
            }
            valueList.add(list);
        }
        {for(int i=index+1;i<num.length;i++)
            {jud[i]=true;
                dfs(num, i, valueList,jud);
                jud[i]=false;
            
            }
        }
    }
}

题目形容(力扣 90 题)：

给定一个可能蕴含反复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

阐明：解集不能蕴含反复的子集。

示例:

输出: [1,2,2]
输入:
[[2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []]

和下面无反复数组求子集不同的是这外面 可能会呈现反复的元素。咱们须要在后果中过滤掉反复的元素。

首先，子集问题无疑是应用回溯法求得后果，首先剖析如果序列没有反复的状况，咱们会借助一个 boolean[] 数组 标记应用过的元素和 index 示意以后的下标，在进行回溯的时候咱们只向后进行递归并且将枚举到的那个元素 boolean[index]置为 true(回来的时候还原)。每次递归收集 boolean[]数组中 true 的元素为其中一个子集。

而有反复元素的解决上，和后面全排列的解决很类似，首 先进行排序 ，而后在进行递归解决的时候遇到雷同元素只容许从第一位间断应用而不容许跳着应用，所以在递归向下时候须要判断是否满足条件( 第一个元素 或和前一个不同 或和 前一个同且前一个已应用)，具体能够参考这张图：

实现代码为：

class Solution {public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);
    boolean jud[]=new boolean[nums.length];
    List<List<Integer>> valueList=new ArrayList<List<Integer>>();
    dfs(nums,-1,valueList,jud);
    return valueList;
  }

    private void dfs(int[] nums, int index, List<List<Integer>> valueList, boolean[] jud)   {
        // TODO Auto-generated method stub
        List<Integer>list=new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++)
        {if (jud[i]) {list.add(nums[i]);
            }
        }
        valueList.add(list);
        for(int i=index+1;i<nums.length;i++)
        {// 第一个元素 或 以后元素不和后面雷同  或者雷同且后面被应用了能够持续进行
            if((i==0)||(nums[i]!=nums[i-1])||(i>0&&jud[i-1]&&nums[i]==nums[i-1]))
            {jud[i]=true;
                dfs(nums, i, valueList,jud);
                jud[i]=false;
            }
        }
    }
}

到这里，本篇的全排列、组合、子集问题就介绍到这里啦，尤其要留神问题解决去重的思路和策略。当然和这相似的问题也是很多啦，多刷一刷就能够很好的把握，前面敬请期待！

原创不易，bigsai 请思否的敌人们帮两件事帮忙一下:

点赞、珍藏、关注 反对一下，您的必定是我创作的源源能源。
微信搜寻「bigsai」，关注我的原创技术公众号，后退路线上不迷路！

咱们下次再见！

正文完

算法

发表至：算法

2021-03-12

0

关于算法:SLAM技术支持的物体6Dof位姿估计的自训练方法

关于算法:动态规划系列-背包DP之01背包

关于算法:实时渲染实时离线云渲染混合渲染的区别

关于算法:MATH-523线性模型

关于音视频:融云聊天室属性-kv

关于算法:一文拿捏全排列组合子集问题

前言

全排列问题

无反复序列的全排列

有反复序列的全排列

组合问题

子集

无反复数组子集

有反复数组子集

结语

站内搜索