T47. Permutations II【Medium】

題目

給出一個可以包含重復(fù)數(shù)字的數(shù)字集，返回所有可能的不重復(fù)排列組合。

例如，
[1,1,2] 有如下的排列組合：

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

這題的大體想法和上題一樣，不過除了遞歸，這題還要對重復(fù)怎么判斷進行處理，以及防止重復(fù)排列組合的出現(xiàn)。

① 遞歸

思路和上一題差不多，如下：

排列組合（1 2 3）
= 1 + 排列組合（2 3）∪ 2 + 排列組合（1 3）∪ 3 + 排列組合（1 2）
排列組合（2 3）
= 2 + 排列組合（3）∪ 3 + 排列組合（2）
= 23 ∪ 32 

可以看出在數(shù)字只有一個的時候到了遞歸的終點

② 重復(fù)判別

上一題是直接看這個數(shù)有沒有用過，那是基于這個數(shù)只出現(xiàn)一遍，而在這題可以出現(xiàn)重復(fù)的數(shù)字這個方法就不可用了。這個 Solution 用了什么解決方法呢，看下面：

boolean[] used = new boolean[nums.length];

建立了一個 boolean 的數(shù)組和 nums 中的數(shù)一一對應(yīng),然后用

used[i]=true;
used[i]=false;

的設(shè)置來表示這個數(shù)是否用過

然后用在循環(huán)中加入下面的語句來跳過用過的數(shù)字

if(used[i]) continue;

③ 排除重復(fù)排列組合

造成重復(fù)排列組合的原因可以動手寫一下看看~

避免這種重復(fù)的方法在于后面重復(fù)的數(shù)不能排在前面重復(fù)的數(shù)前面（可能有點繞，最好動手寫寫看）。

代碼則是很簡單，像下面這樣：

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

因為已經(jīng)排好序了，所以若 nums[i-1]==nums[i] 和 !used[i-1] 則代表它之前的重復(fù)的數(shù)沒有被用到，這時，跳過這次循環(huán)，因為它也不應(yīng)該被用。

另外，不能寫成

if(i>0 &nums[i-1]==nums[i] & !used[i-1]) continue;

可以想一下原因~我在補充里說！

代碼

代碼取自 Top Solution，稍作注釋

public List<List<Integer>> permuteUnique(int[] nums) {
        //建立要返回的數(shù)據(jù)形式
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //若為空,直接返回
        if(nums==null || nums.length==0) return res;
        //建立 used 數(shù)組來判斷這個數(shù)字是否用過
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        //排序
        Arrays.sort(nums);
        dfs(nums, used, list, res);
        return res;
    }

public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
        //若所有元素都用到了(達到長度)則加到 ArrayList 里面
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //若用到過這個數(shù)字了,則跳過本次循環(huán)
            if(used[i]) continue;
            //用這句來避免重復(fù)
            if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            //設(shè)置為true代表已經(jīng)用過
            used[i]=true;
            //下面四行是遞歸,看和上一題差不多,看"思路"里
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i]=false;
            list.remove(list.size()-1);
        }
    } 

補充

關(guān)于

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

為什么要用 "&&" 而不用 "&"?

我們可以嘗試先把 "&&" 改成 "&"，然后發(fā)現(xiàn)會報錯！

為什么呢？我的編譯器不愛我了嗎？

這要先講一下兩者的區(qū)別：

&&和&都是表示與，區(qū)別是&&只要第一個條件不滿足，后面條件就不再判斷。而&要對所有的條件都進行判斷。

因為當(dāng)用了 && 時，執(zhí)行 i>0 為 false 時就不往下執(zhí)行了，而用 & 時會把這三個都執(zhí)行一遍，在執(zhí)行

nums[i-1]==nums[i]

的時候 nums[i-1] 是 nums[-1],會報 ArrayIndexOutOfBoundsException 的錯誤。