http://www.lintcode.com/en/problem/permutations-ii/#

the idea is similar with the subsets II. but we need to remember the occurance of each item in the current sets(whether has the array index been visited). and same logic, we need to sort the array, and if the nth dup is picked up when the (n - 1)th is not, we continue.

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null) {
            return ans;
        }

        List<Integer> cur = new ArrayList<>();

        Arrays.sort(nums);


        int[] visited = new int[nums.length];
        helper(ans, cur, nums, visited);

        return ans;
    } 

    private void helper(List<List<Integer>> ans,
                        List<Integer> cur,
                        int[] nums,
                        int[] visited) {

        if (cur.size() == nums.length) {
            ans.add(new ArrayList<Integer>(cur));
            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;
            }

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


    }
}