package com.jiucaiyuan.net.question;



import java.util.ArrayList;

import java.util.List;



/**

 *

 * 46.全排列

 *

 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

 *

 * @Author jiucaiyuan  2022/4/14 00:00

 * @mail services@jiucaiyuan.net

 */

class FullPermutation {

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



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

        int[] visited = new int[nums.length];

        backtrack(res, nums, new ArrayList<Integer>(), visited);

        return res;



    }



    private static void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {

        if (tmp.size() == nums.length) {

            res.add(new ArrayList<>(tmp));

            return;

        }

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

            if (visited[i] == 1) continue;

            visited[i] = 1;

            tmp.add(nums[i]);

            backtrack(res, nums, tmp, visited);

            visited[i] = 0;

            tmp.remove(tmp.size() - 1);

        }

    }



    public static void main(String[] args) {

        int[] nums = {1,2,3,4,5};

        List<List<Integer>> res = permute(nums);

        for(int i=0;i<res.size();i++){

            System.out.println(res.get(i));

        }

    }

}