LeetCode 47.Permutations II

Question

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

Explanation

和之前一道题相似，只是注意一下这里是可以重复的。

Code

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int[] visited = new int[nums.length];
        if (nums == null || nums.length == 0) return result;
        for (int i=0; i<nums.length; i++) {
            visited[i] = 0;
        }
        Arrays.sort(nums);
        helper(nums, new ArrayList<Integer>(), result, visited);
        return result;

    }


    public void helper(int[] nums,  List<Integer> list, List<List<Integer>> result, int[] visited) {
        if (list.size() == nums.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i=0; i<nums.length; i++) {
            // 判断是否访问过，或者是否排在前面的相同的没有使用。
            if (visited[i] == 1 || (i!=0 && nums[i] == nums[i-1]&& visited[i-1] == 0)) continue;
            visited[i] = 1;

            list.add(nums[i]);
            helper(nums, list, result, visited);
            list.remove(list.size()-1);
            visited[i] = 0;
        }  

    }
}