Thinking process

when to add same value? and when not to?

• add the same value if the previous one has been visited

MIstakes

1. Don't forget to sort!!!!

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //validate input
        if (nums.length == 0) return result;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        permuteDfsHelper(nums, result, new ArrayList<Integer>(), visited);

        return result;
    }

    private void permuteDfsHelper(int[] nums, List<List<Integer>> result, List<Integer> list, boolean[] visited) {
        //end conditions
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            if (visited[i] || (i > 0 && !visited[i - 1] && nums[i] == nums[i - 1])) continue;
            list.add(nums[i]);
            visited[i] = true;
            permuteDfsHelper(nums, result, list, visited);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}