全排列2

题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

解题思路

和全排列类似写法，因要求不能重复，所以在剪枝方面需要考虑更多。
首先重复数字得到的排列结果也是一样的，所以遇到重复数字跳过即可。

1. 排序后用 nums[i] == nums[i - 1];来判读是否遇到重复数字。
2. 用visited[i - 1] != 1; 来判断上一个数字是否刚刚被回溯。

代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List res = new ArrayList();
        int[] visited = new int[nums.length];
        Arrays.sort(nums);
        getRes(res,nums,visited,new ArrayList());
        return res;
    }
    public void getRes(List res,int[] nums, int[] visited,List temp){
        if (temp.size() == nums.length){
            res.add(new ArrayList(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (visited[i] == 1) continue;
            if (i > 0 && nums[i] == nums[i - 1] && visited[i-1] != 1) continue;
            visited[i] = 1;
            temp.add(nums[i]);
            getRes(res,nums,visited,temp);
            visited[i] = 0;
            temp.remove(temp.size()-1);
        }
    }
}