47. 全排列II

回溯

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {

    List> list = new LinkedList<>();
    LinkedList li = new LinkedList<>();

    public List> permuteUnique(int[] nums) {

        /**
         * 去重前先排序
         */
        int[] used = new int[nums.length];
        Arrays.sort(nums);
        backtracking(nums, used);
        return list;
    }

    /**
     * 排列问题不需要startIndex，因为每次都需要从头开始遍历
     * 但是需要used数组记录当前使用过哪些元素
     */
    public void backtracking(int[] nums, int[] used){

        /**
         * 终止条件
         * 列表大小等于原数组大小
         */
        if (li.size() == nums.length){

            list.add(new LinkedList<>(li));
            return;
        }

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

            /**
             * 每次循环都从0开始，如果当前元素使用过，在同一枝不能再选择
             * 如果相邻的元素相等，且前面的元素used[i - 1] == 0，说明前面的元素肯定已经作为队首排过序，并且回溯了（因为循环是从左到右的，前面的元素肯定先被处理）
             * 在一层循环结束后同时对used数组回溯，因为下一次循环又是全新的排列
             * used[i - 1] == 1，说明同?树?nums[i - 1]使?过
             * used[i - 1] == 0，说明同?树层nums[i - 1]使?过，要跳过
             */
            if (used[i] == 1 || i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0){
                continue;
            }

            li.add(nums[i]);
            used[i] = 1;
            backtracking(nums, used);
            li.removeLast();
            used[i] = 0;
        }
    }
}

/**
 * 时间复杂度 O(n×n!)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/permutations-ii/