LeetCode Permutations II

47.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],
  [2,1,1]
]

方法

明显使用dfs，但是会超时，看看怎么能通过剪枝来减少判断。

由于数组中有数字重复，则将数组进行排序，相同的数字会邻近,这样可以略过相同数字的情况，剪枝。

判断，若num[i-1]==num[i],当num[i-1]没使用过时，说明num[i]的置换的全部样例可以由num[i-1]获得，则下面的程序不执行。相反，当num[i-1]使用过时，表示后面的数字并没有执行过，需要继续dfs

public class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length == 0){
            return new ArrayList<List<Integer>>();
        }
        boolean[] b = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums,new ArrayList<Integer>(),b);
        return list;
    }
    public void dfs(int[] nums, ArrayList<Integer> array, boolean[] b){
        if(array.size() == nums.length){
            if(!list.contains(array)){
                list.add(new ArrayList<Integer>(array));
            }
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i-1] == nums[i] && !b[i-1]){
                continue;
            }
            if(b[i] == false){
                b[i] = true;
                array.add(nums[i]);
                dfs(nums,array,b);
                b[i] = false;
                array.remove(array.size()-1);
            }
        }
    }
}