Leetcode 46: full arrangement

link

Ideas ： to flash back

Multitree framework ：

Backtracking framework ：

Backtracking algorithm is pure violence ！

First fix the number one as 1, And the second one could be 2, So the third place can only be 3; And then you can turn the second one into 3, The third can only be 2 了 ; And then you can only change the first one , become 2, And then the last two …… In fact, this is the backtracking algorithm

It can be regarded as a multi fork tree ！
use path Record the nodes traversed , When traversing to the leaf node path Deposit in res Just go back up ,
Every time you return up one layer, you will path Delete a node at the end of , In order to maintain path;

use onPath Boolean array records the traversal on a single line to avoid repetition ,

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){
    
        // Termination conditions 
        if(path.size()==nums.length){
    
            res.add(new LinkedList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
    
            if(onPath[i]){
     //  If it has been traversed 
                continue;
            }
            // Make a choice before recursion 
            onPath[i]=true;
            path.add(nums[i]);
            // Go to the next level 
            dfs(nums,path,onPath);
			// Undo selection after recursion 
            onPath[i]=false;
            path.removeLast();
        }
    }
}

Or directly path.contains(nums[i]) To judge ：

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){
    
        // Termination conditions 
        if(path.size()==nums.length){
    
            res.add(new LinkedList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
    
            if(path.contains(nums[i])){
     //  If it has been traversed 
                continue;
            }
            // Make a choice before recursion 
            path.add(nums[i]);
            // Go to the next level 
            dfs(nums,path);
            // Undo selection after recursion 
            path.removeLast();
        }
    }
}