LeetCode 46：全排列

链接

思路：回溯

多叉树框架：

回溯框架：

回溯算法就是纯暴力穷举 ！

先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……其实这就是回溯算法

可以看作是一棵多叉树 ！
用path记录遍历的节点，当遍历到叶子节点时将path存入res 就向上返回，
每向上返回一层就将path的末尾删除一个节点，以此维护path；

用onPath布尔数组记录单条线路上的遍历情况避免重复，

class Solution {
    
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
    
        int n=nums.length;
        boolean[] onPath=new boolean[n];
        res=new LinkedList<>();
        LinkedList<Integer> path=new LinkedList<>();
        dfs(nums,path,onPath);
        return res;
    }

    void dfs(int[] nums,LinkedList<Integer> path, boolean[] onPath){
    
        //终止条件
        if(path.size()==nums.length){
    
            res.add(new LinkedList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
    
            if(onPath[i]){
     // 若已遍历过
                continue;
            }
            //递归之前做选择
            onPath[i]=true;
            path.add(nums[i]);
            //进入下一层
            dfs(nums,path,onPath);
			//递归之后撤销选择
            onPath[i]=false;
            path.removeLast();
        }
    }
}

或直接用path.contains(nums[i]) 来判断：

class Solution {
    
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
    
        int n=nums.length;
        res=new LinkedList<>();
        LinkedList<Integer> path=new LinkedList<>();
        dfs(nums,path);
        return res;
    }

    void dfs(int[] nums,LinkedList<Integer> path){
    
        //终止条件
        if(path.size()==nums.length){
    
            res.add(new LinkedList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
    
            if(path.contains(nums[i])){
     // 若已遍历过
                continue;
            }
            //递归之前做选择
            path.add(nums[i]);
            //进入下一层
            dfs(nums,path);
            //递归之后撤销选择
            path.removeLast();
        }
    }
}