2017-04-11 15:42:08 +0000   |     algorithm leetcode backtracking   |   Viewed times   |    

题目

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

标准回溯算法

和无重复数字Permutations的区别在于,得先排序,然后跳过重复数字。比如[1,2,1],先排序,得到[1,1,2]。然后递归遍历的时候处理过第一个1以后,跳过第二个1,直接处理2

代码

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> buff = new ArrayList<>();
        List<Integer> candidates = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            candidates.add(nums[i]);
        }
        backtracking(buff,candidates,result);
        return result;
    }
    public void backtracking(List<Integer> buff, List<Integer> candidates, List<List<Integer>> result) {
        if (candidates.size() == 0) { result.add(new ArrayList<Integer>(buff)); return; }
        for (int i = 0; i < candidates.size(); i++) {
            int temp = candidates.get(i);
            buff.add(temp);
            candidates.remove(i);
            backtracking(buff,candidates,result);
            candidates.add(i,temp);
            buff.remove(buff.size()-1);
            while (i+1 < candidates.size() && candidates.get(i+1).equals(candidates.get(i))) { i++; } // skip duplicates
        }
    }
}

结果

银弹! permutation-2-1