首页 > 代码库 > LeetCode Permutations II

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].

思路分析:Permutation的题目都可以formalize成Search问题来解,当我们把数组排序后,可以从空集开始,不断添加没有使用过的数字形成新的set,直到这个set的长度等于num数组的长度那么就找到了一个Permutation。用DFS搜索解比较直接。但是这题要注意判断重复数字的情况,对于排序后的数组从前向后迭代,重复数字肯定是相邻数字,那么如果当前数字等于前一个相邻数字而前一个数字没有使用,说明添加这个数字到尾部所形成的分支已经在之前搜索过,不必再搜索一次,可以剪掉,直接返回。为了深入理解这个DFS搜索的过程,我画出了针对两个简单输入例子的搜索树。给出了没有重复数字(1 2 3)和有重复数字(1 1 2)针对Permutation的搜索过程。另外,这题还要注意向结果List中添加新的Permutation时要添加拷贝而不是原来的对象引用,否则后面对state的操作会覆盖之前添加的Permutation,这是很容易犯的的错误,要特别小心。

这题的Code也可以没有重复数字的情况 ,也就是LeetCode Permutations问题。



AC Code

public class Solution {
    
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(num == null || num.length == 0){
            return res;
        }
        Arrays.sort(num);
        List<Integer> state = new ArrayList<Integer>();
        dfs(res, state, num, new boolean[num.length]);
        return res;
    }
    
    void dfs(List<List<Integer>> res, List<Integer> state, int [] num, boolean [] used){
        if(state.size() == num.length){
            res.add(new ArrayList(state));//add a copy
            return;
        } 
        for(int i = 0; i < num.length; i++){
            if(i > 0 && !used[i-1] && num[i] == num[i-1]) continue;// judge duplicate number
            if(!used[i]){
                state.add(num[i]);
                used[i] = true;
                dfs(res, state, num, used);
                state.remove(state.size() - 1);
                used[i] = false;
            }
        }
    }
}


LeetCode Permutations II