import java.util.*;

public class PermuteUnique_47 {

/**

* 使用回溯+减枝求解

* @param nums

* @return

*/

public List<List<Integer>> permuteUnique(int[] nums) {

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

if (nums == null && nums.length == 0) {

return res;

}

// 对数组排序方便剪枝条件判断

Arrays.sort(nums);

Deque<Integer> path = new ArrayDeque<>();

boolean[] used = new boolean[nums.length];

backtrack(0, used, nums, path, res);

return res;

}

private void backtrack(int index, boolean[] used, int[] nums, Deque<Integer> path, List<List<Integer>> res) {

if (index == nums.length) {

res.add(new ArrayList<Integer>(path));

return;

}

for (int i = 0; i < nums.length; i++) {

if (used[i]) {

continue;

}

// 减枝去重

// 当前选择的节点等于前一个节点的值

// 前一个节点已经被回退撤销

if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {

continue;

}

path.addLast(nums[i]);

used[i] = true;

backtrack(index + 1, used, nums, path, res);

used[i] = false;

path.removeLast();

}

}

}