LeetCode Q 47 - Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example: Input: [1,1,2] ; Output: [ [1,1,2], [1,2,1], [2,1,1] ]

Solution : Backtracking

Tips:

Use an extra boolean array boolean[] used to indicate whether the value is added to list.
Sort the array int[] nums to make sure we can skip the same value.
When a number has the same value with its previous, we can use this number only if his previous is used.

Code:

private List<List<Integer>> res;
public List<List<Integer>> permute(int[] nums) {
  res = new ArrayList<>();
  if (nums == null || nums.length == 0) return res;
  Arrays.sort(nums);
  boolean[] visited = new boolean[nums.length];
  backtrack(nums, new ArrayList<>(), visited);
  return res;
}

private void backtrack(int[] nums, List<Integer> temp, boolean[] visited) {
  if (temp.size() == nums.length) {
    res.add(new ArrayList(temp)); return;
  }
  
  for (int i = 0; i < nums.length; i++) {
    if (visited[i] || i > 0 && nums[i] = nums[i - 1] && !visited[i - 1]) continue;
    visited[i] = true;
    temp.add(nums[i]);
    backtrack(nums, temp, visited);
    temp.remove(temp.size() - 1);
    visited[i] = false;
  }
}

Tips:
When backtracking, using !visited[i - 1] or using visited[i - 1] is all correct. But using !visited[i - 1] is more efficient! These two figures can explain the reason !visited[i - 1], visited[i - 1].