package pers.vic.basics.leetcode;

import java.util.*;

/**
 * @description: 46. 全排列  {@literal https://leetcode-cn.com/problems/permutations/} 回溯
 * @author Vic.xu
 * @date: 2020/12/9 10:31
 */
public class J0046_M_Permute {
    /*
    给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     */

    /**
     * 已经对回溯有所了解，这些的问题应该好解决
     */
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        dfs(nums, res, new ArrayDeque<Integer>(len), new boolean[len], len);
        return res;
    }

    /**
     * 把每个位置的的数字罗列出来即可
     */
    public static void dfs(int[] nums, List<List<Integer>> res, Deque<Integer> temp, boolean[] used, int len){
        if (temp.size() == len) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < len; i++) {
            //当前下标是否已经被使用
            if (used[i]){
                continue;
            }
            used[i] = true;
            temp.add(nums[i]);
            dfs(nums, res, temp, used, len);
            //状态恢复
            used[i] = false;
            temp.removeLast();
        }
    }

    public static void main(String[] args) {
        permute(new int[]{1,2,3}).forEach(System.out::println);
    }


}