循环递归，回溯

class Solution {
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    boolean[] used = new boolean[1024];// nums中第i个元素是否使用过，添加到path中

public List<List<Integer>> permutation(int[] nums) {
    res.clear();
    if (nums.length == 0) {
        return res;
    }
    Arrays.sort(nums);
    generatePermutation(nums, 0, new LinkedList<>());
    return res;

}

// path保存了一个有index个元素的排列
// 向这个排列的末尾添加第index+1个元素，获得一个有index+1个元素的排列
private void generatePermutation(int[] nums, int index, List<Integer> path) {
    // boolean[] used = new boolean[nums.length];// nums中第i个元素是否使用过，添加到path中
    if (index == nums.length) {
        res.add(new ArrayList<Integer>(path));
        return;
    }

    // 循环加递归！！就是回溯！！
    for (int i = 0; i < nums.length; i++) {
        if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }

            path.add(nums[i]);
            used[i] = true;
            // 尝试着将所有剩余没有用过的元素添加到path中去，将所有没有用过的元素，添加到index位置
            // 可以这样理解，在循环中，只有i是变化的，index是不变的，因此就可以看作是将所有的元素遍历一遍，尝试添加到index位置上
            generatePermutation(nums, index + 1, path);
            // 回复状态,添加循环后的另一个元素，将循环遍历的所有元素都尝试添加一遍，回溯
            path.remove(index);
            used[i] = false;

    }
}

}