給女朋友這樣講全排列、組合、子集問題,下次再也不鬧了
本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」,作者bigsai。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。
前言
Hello,大家好,long time no see!在刷題和面試過程中,我們經(jīng)常遇到一些排列組合類的問題,而全排列、組合、子集等問題更是非常經(jīng)典問題。本篇文章就帶你徹底搞懂全排列!
求全排列?
全排列即:n個(gè)元素取n個(gè)元素(所有元素)的所有排列組合情況。
求組合?
組合即:n個(gè)元素取m個(gè)元素的所有組合情況(非排列)。
求子集?
子集即:n個(gè)元素的所有子集(所有可能的組合情況)。
總的來說全排列數(shù)值個(gè)數(shù)是所有元素,不同的是排列順序;而組合是選取固定個(gè)數(shù)的組合情況(不看排列);子集是對(duì)組合拓展,所有可能的組合情況(同不考慮排列)。
當(dāng)然,這三種問題,有相似之處又略有所不同,我們接觸到的全排列可能更多,所以你可以把組合和子集問題認(rèn)為是全排列的拓展變形。且問題可能會(huì)遇到待處理字符是否有重復(fù)的情況。采取不同的策略去去重也是相當(dāng)關(guān)鍵和重要的!在各個(gè)問題的具體求解上方法可能不少,在全排列上最流行的就是鄰里互換法和回溯法,而其他的組合和子集問題是經(jīng)典回溯問題。而本篇最重要和基礎(chǔ)的就是要掌握這兩種方法實(shí)現(xiàn)的無重復(fù)全排列,其他的都是基于這個(gè)進(jìn)行變換和拓展。
全排列問題
全排列,元素總數(shù)為最大,不同是排列的順序。
無重復(fù)序列的全排列
這個(gè)問題剛好在力扣46題是原題的,大家學(xué)完可以去a試試。
問題描述:
給定一個(gè) 沒有重復(fù) 數(shù)字的序列,返回其所有可能的全排列。
示例:
- 輸入: [1,2,3]
- 輸出:
- [
- [1,2,3],
- [1,3,2],
- [2,1,3],
- [2,3,1],
- [3,1,2],
- [3,2,1]
- ]
回溯法實(shí)現(xiàn)無重復(fù)全排列
回溯算法用來解決搜索問題,而全排列剛好也是一種搜索問題,先回顧一下什么是回溯算法:
回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過程,主要是在搜索嘗試過程中尋找問題的解,當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí),就“回溯”返回,嘗試別的路徑.
而全排列剛好可以使用試探的方法去枚舉所有中可能性。一個(gè)長(zhǎng)度為n的序列或者集合。它的所有排列組合的可能性共有n!種。具體的試探策略如下:
- 從待選集合中選取第一個(gè)元素(共有n種情況),并標(biāo)記該元素已經(jīng)被使用不能再使用。
- 在步驟1的基礎(chǔ)上進(jìn)行遞歸到下一層,從剩余n-1個(gè)元素中按照1的方法找到一個(gè)元素并標(biāo)記,繼續(xù)向下遞歸。
- 當(dāng)所有元素被標(biāo)記后,順序收集被標(biāo)記的元素存儲(chǔ)到結(jié)果中,當(dāng)前層遞歸結(jié)束,回到上一層(同時(shí)將當(dāng)前層標(biāo)記的元素清除標(biāo)記)。這樣一直執(zhí)行到最后。
回溯的流程如果從偽代碼流程大致為這樣:
- 遞歸函數(shù):
- 如果集合所有元素被標(biāo)記:
- 將臨時(shí)儲(chǔ)存添加到結(jié)果集中
- 否則:
- 從集合中未標(biāo)記的元素中選取一個(gè)存儲(chǔ)到臨時(shí)集合中
- 標(biāo)記該元素被使用
- 下一層遞歸函數(shù)
- (這層遞歸結(jié)束)標(biāo)記該元素未被使用
如果用序列 1 2 3 4來表示這么回溯的一個(gè)過程,可以用這張圖來顯示:
回溯過程
用代碼來實(shí)現(xiàn)思路也是比較多的,需要一個(gè)List去存儲(chǔ)臨時(shí)結(jié)果是很有必要的,但是對(duì)于原集合我們標(biāo)記也有兩種處理思路,第一種是使用List存儲(chǔ)集合,使用過就移除然后遞歸下一層,遞歸完畢后再添加到原來位置。另一種思路就是使用固定數(shù)組存儲(chǔ),使用過對(duì)應(yīng)位置使用一個(gè)boolean數(shù)組對(duì)應(yīng)位置標(biāo)記一下,遞歸結(jié)束后再還原。因?yàn)長(zhǎng)ist頻繁查找插入刪除效率一般比較低,所以我們一般使用一個(gè)boolean數(shù)組去標(biāo)記該位置元素是否被使用。
具體實(shí)現(xiàn)的代碼為:
- List<List<Integer>> list;
- public List<List<Integer>> permuteUnique(int[] nums) {
- list=new ArrayList<List<Integer>>();//最終的結(jié)果
- List<Integer> team=new ArrayList<Integer>();//回溯過程收集元素
- boolean jud[]=new boolean[nums.length];//用來標(biāo)記
- 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]) //當(dāng)前數(shù)字被用過 當(dāng)前即不可用
- continue;
- team.add(nums[i]);
- jud[i]=true;//標(biāo)記該元素被使用
- dfs(jud, nums, team, index + 1);
- jud[i] = false;// 還原
- team.remove(index);//將結(jié)果移除臨時(shí)集合
- }
- }
修改一下輸出的結(jié)果和上面思維導(dǎo)圖也是一致的:
鄰里互換法實(shí)現(xiàn)無重復(fù)全排列
回溯的測(cè)試是試探性填充,是對(duì)每個(gè)位置進(jìn)行單獨(dú)考慮賦值。而鄰里互換的方法雖然是也是遞歸實(shí)現(xiàn)的,但是他是一種基于交換的策略和思路。而理解起來也是非常簡(jiǎn)單,鄰里互換的思路是從左向右進(jìn)行考慮。
因?yàn)樾蛄惺菦]有重復(fù)的,我們開始將數(shù)組分成兩個(gè)部分:暫時(shí)確定部分和未確定部分。開始的時(shí)候均是未確定部分,我們需要妥善處理的就是未確定部分。在未確定部分的序列中,我們需要讓后面未確定的每一位都有機(jī)會(huì)處在未確定的首位,所以未確定部分的第一個(gè)元素就要和每一個(gè)依次進(jìn)行交換(包括自己),交換完成之后再向下進(jìn)行遞歸求解其他的可能性,求解完畢之后要交換回來(還原)再和后面的進(jìn)行交換。這樣當(dāng)遞歸進(jìn)行到最后一層的時(shí)候就將數(shù)組的值添加到結(jié)果集中。如果不理解可以參考下圖進(jìn)行理解:
鄰里互換部分過程
實(shí)現(xiàn)代碼為:
- 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)//到最后一個(gè) 添加到結(jié)果中
- {
- 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;
- }
- }
那么鄰里互換和回溯求解的全排列有什么區(qū)別呢?首先回溯法求得的全排列如果這個(gè)序列有序得到的結(jié)果是字典序的,因?yàn)槠洳呗允翘畛?,先小后大有序,而鄰里互換沒有這個(gè)特征。其次鄰里互換在這種情況下的效率要高于回溯算法的,雖然量級(jí)差不多但是回溯算法需要維護(hù)一個(gè)集合頻繁增刪等占用一定的資源。
有重復(fù)序列的全排列
有重復(fù)對(duì)應(yīng)的是力扣第47題 ,題目描述為:
給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ,按任意順序 返回所有不重復(fù)的全排列。
示例 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
這個(gè)和上面不重復(fù)的全排列略有不同,這個(gè)輸入數(shù)組中可能包含重復(fù)的序列,我們?cè)趺礃硬扇『线m的策略去重復(fù)才是至關(guān)重要的。我們同樣針對(duì)回溯和鄰里互換兩種方法進(jìn)行分析。
回溯剪枝法
因?yàn)榛厮萃暾谋戎苯舆f歸慢,所以剛開始并沒有考慮使用回溯算法,但是這里用回溯剪枝相比遞歸鄰里互換方法更好一些,對(duì)于不使用哈希去重的方法,首先進(jìn)行排序預(yù)處理是沒有懸念的,而回溯法去重的關(guān)鍵就是避免相同的數(shù)字因?yàn)橄鄬?duì)次序問題造成重復(fù),所以在這里相同數(shù)字在使用上相對(duì)位置必須不變,而具體剪枝條的規(guī)則如下:
- 先對(duì)序列進(jìn)行排序
- 試探性將數(shù)據(jù)放到當(dāng)前位置
- 如果當(dāng)前位置數(shù)字已經(jīng)被使用,那么不可使用
- 如果當(dāng)前數(shù)字和前一個(gè)相等但是前一個(gè)沒有被使用,那么當(dāng)前不能使用,需要使用前一個(gè)數(shù)字。
回溯選取策略
思路很簡(jiǎn)單,實(shí)現(xiàn)起來也很簡(jiǎn)單:
- 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])) //當(dāng)前數(shù)字被用過 或者前一個(gè)相等的還沒用,當(dāng)前即不可用
- continue;
- team.add(nums[i]);
- jud[i]=true;
- dfs(jud, nums, team, index + 1);
- jud[i] = false;// 還原
- team.remove(index);
- }
- }
鄰里互換法
我們?cè)趫?zhí)行遞歸全排列的時(shí)候,主要考的是要把重復(fù)的情況搞下去,鄰里互換又要怎么去重呢?
使用HashSet這種方式這里就不討論啦,我們?cè)谶M(jìn)行交換swap的時(shí)候從前往后,前面的確定之后就不會(huì)在動(dòng),所以我們要慎重考慮和誰交換。比如1 1 2 3第一個(gè)數(shù)有三種情況而不是四種情況(兩個(gè)1 1 2 3為一個(gè)結(jié)果):
- 1 1 2 3 // 0 0位置交換
- 2 1 1 3 // 0 2位置交換
- 3 1 2 1 // 0 3位置交換
另外比如3 1 1序列,3和自己交換,和后面兩個(gè)1只能和其中一個(gè)進(jìn)行交換,我們這里可以約定和第一個(gè)出現(xiàn)的進(jìn)行交換,我們看一個(gè)圖解部分過程:
鄰里互換一個(gè)過程
所以,當(dāng)我們從一個(gè)index開始的時(shí)候要記住以下的規(guī)則:同一個(gè)數(shù)只交換一次(包括值等于自己的數(shù))。在判斷后面值是否出現(xiàn)的時(shí)候,你可以遍歷,也可以使用hashSet().當(dāng)然這種方法的痛點(diǎn)就是判斷后面出現(xiàn)的數(shù)字效率較低。所以在可能重復(fù)的情況這種方法效率一般般。
具體實(shí)現(xiàn)的代碼為:
- 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;
- }
組合問題
組合問題可以認(rèn)為是全排列的變種,問題描述(力扣77題):
給定兩個(gè)整數(shù) n 和 k,返回 1 … n 中所有可能的 k 個(gè)數(shù)的組合。
示例:
- 輸入: n = 4, k = 2
- 輸出:
- [
- [2,4],
- [3,4],
- [2,3],
- [1,2],
- [1,3],
- [1,4],
- ]
分析:
這個(gè)問題經(jīng)典回溯問題。組合需要記住只看元素而不看元素的順序,比如a b和b a是同一個(gè)組合。要避免這樣的重復(fù)是核心,而避免這樣的重復(fù),需要借助一個(gè)int類型保存當(dāng)前選擇元素的位置,下次只能遍歷選取下標(biāo)位置后面的數(shù)字,而k個(gè)數(shù),可以通過一個(gè)數(shù)字類型來記錄回溯到當(dāng)前層處理數(shù)字的個(gè)數(shù)來控制。
全排列和組合的一些區(qū)別
具體實(shí)現(xiàn)也很容易,需要?jiǎng)?chuàng)建一個(gè)數(shù)組儲(chǔ)存對(duì)應(yīng)數(shù)字,用boolean數(shù)組判斷對(duì)應(yīng)位置數(shù)字是否使用,這里就不用List存儲(chǔ)數(shù)字了,最后通過判斷boolean數(shù)組將數(shù)值添加到結(jié)果中也是可行的。實(shí)現(xiàn)代碼為:
- class Solution {
- public List<List<Integer>> combine(int n, int k) {
- List<List<Integer>> valueList=new ArrayList<List<Integer>>();//結(jié)果
- int num[]=new int[n];//數(shù)組存儲(chǔ)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個(gè)元素滿
- {
- 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;//還原
- }
- }
- }
- }
子集
子集問題和組合有些相似。這里講解數(shù)組中無重復(fù)和有重復(fù)的兩種情況。
無重復(fù)數(shù)組子集
問題描述(力扣78題):
給你一個(gè)整數(shù)數(shù)組 nums ,數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集(冪集)。
解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。
示例 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 中的所有元素 互不相同
子集和上面的組合有些相似,當(dāng)然我們不需要判斷有多少個(gè),只需要按照組合回溯的策略遞歸進(jìn)行到最后,每進(jìn)行的一次遞歸函數(shù)都是一種情況都要加入到結(jié)果中(因?yàn)椴扇〉牟呗圆粫?huì)有重復(fù)的情況)。
實(shí)現(xiàn)的代碼為:
- 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[]) {
- {//每進(jìn)行遞歸函數(shù)都要加入到結(jié)果中
- 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;
- }
- }
- }
- }
有重復(fù)數(shù)組子集
題目描述(力扣90題):
給定一個(gè)可能包含重復(fù)元素的整數(shù)數(shù)組 nums,返回該數(shù)組所有可能的子集(冪集)。
說明:解集不能包含重復(fù)的子集。
示例:
- 輸入: [1,2,2]
- 輸出:
- [
- [2],
- [1],
- [1,2,2],
- [2,2],
- [1,2],
- []
- ]
和上面無重復(fù)數(shù)組求子集不同的是這里面可能會(huì)出現(xiàn)重復(fù)的元素。我們需要在結(jié)果中過濾掉重復(fù)的元素。
首先,子集問題無疑是使用回溯法求得結(jié)果,首先分析如果序列沒有重復(fù)的情況,我們會(huì)借助一個(gè)boolean[]數(shù)組標(biāo)記使用過的元素和index表示當(dāng)前的下標(biāo),在進(jìn)行回溯的時(shí)候我們只向后進(jìn)行遞歸并且將枚舉到的那個(gè)元素boolean[index]置為true(回來的時(shí)候復(fù)原)。每次遞歸收集boolean[]數(shù)組中true的元素為其中一個(gè)子集。
在這里插入圖片描述
而有重復(fù)元素的處理上,和前面全排列的處理很相似,首先進(jìn)行排序,然后在進(jìn)行遞歸處理的時(shí)候遇到相同元素只允許從第一位連續(xù)使用而不允許跳著使用,所以在遞歸向下時(shí)候需要判斷是否滿足條件(第一個(gè)元素或和前一個(gè)不同或和前一個(gè)同且前一個(gè)已使用),具體可以參考這張圖:
實(shí)現(xiàn)代碼為:
- 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++)
- {//第一個(gè)元素 或 當(dāng)前元素不和前面相同 或者相同且前面被使用了可以繼續(xù)進(jìn)行
- 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;
- }
- }
- }
- }
結(jié)語
到這里,本篇的全排列、組合、子集問題就介紹到這里啦,尤其要注意問題處理去重的思路和策略。當(dāng)然和這類似的問題也是很多啦,多刷一刷就可以很好的掌握,后面敬請(qǐng)期待!