Leetcode-46. 全排列

46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路
利用回溯算法的框架解题，先做当前选择，然后回溯之后的过程，之后再撤销选择
这样可以遍历所有结果
结束条件就是选择选项为空，不需要再做选择

class Solution {

    List<List<Integer>> res=new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {

        LinkedList<Integer> track=new LinkedList<>();
        backtrack(nums,track);
        return res;


    }

    public void backtrack(int[] nums,LinkedList<Integer> track){
        //结束条件：当前路径为一条全路径--所有元素均在track中
        if(track.size()==nums.length){
            res.add(new LinkedList(track));
            return;
        }
        //其他元素依次选择
        for(int i=0;i<nums.length;i++){
            //如果已经在路径中则跳过
            if(track.contains(nums[i])){
                continue;
            }
            //做选择
            track.add(nums[i]);
            //递归后序
            backtrack(nums,track);
            //撤销选择
            track.removeLast();
        }

    }
}