46. 全排列

回溯

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

class Solution {

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

    public List> permute(int[] nums) {

        int[] used = new int[nums.length];
        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数组回溯，因为下一次循环又是全新的排列
             */
            if (used[i] == 1){
                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/