【LeetCode】Permutations II 解題報告

【題目】

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,

[1,1,2]

 have the following unique permutations:

[1,1,2]

, 

[1,2,1]

, and 

[2,1,1]

.

【解析】

題意：求一個數組的全排列，與【LeetCode】Permutations 解題報告 不同的是，數組中的數有重複。

對于全排列，現在比較常用的算法就是根據 【LeetCode】Next Permutation 解題報告 從小到大逐個找出所有的排列。

算法：回溯、字典序法。

public class Solution {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        
        //首先得把原始數組添加到結果集
        List<Integer> list = new ArrayList<Integer>();
        for (int x : num) {
            list.add(x);
        }
        ans.add(list);
        
        //逐個添加下一個解
        for (int i = 1; i < factorial(num.length); i++) {
            nextPermutation(num);
        }
        
        return ans;
    }
    
    public void nextPermutation(int[] num) {
        //找到最後一個正序
        int i = num.length - 1;
        while (i > 0 && num[i] <= num[i - 1]) {
            i--;
        }
        if (i <= 0) return;
        
        //找到最後一個比num[i-1]大的數
        int j = num.length - 1;
        while (j >= i && num[j] <= num[i - 1]) {
            j--;
        }
        
        //交換
        int tmp = num[i - 1];
        num[i - 1] = num[j];
        num[j] = tmp;
        
        //逆排i-1之後的數
        int l = i, r = num.length - 1;
        while (l < r) {
            tmp = num[l];
            num[l] = num[r];
            num[r] = tmp;
            l++;
            r--;
        }
        
        //添加到結果集
        List<Integer> list = new ArrayList<Integer>();
        for (int x : num) {
            list.add(x);
        }
        ans.add(list);
    }
    
    public int factorial(int n) {
        return n == 0 ? 1 : n * factorial(n - 1);
    }
}
           

相關題目：【LeetCode】Permutations 解題報告 和 【LeetCode】Next Permutation 解題報告