전체 배열 1 및 2

题目：全排列1  全排列2

解题思路：

回溯法，有大佬总结了回溯法的模板，在这里借用，链接：回溯法

在递归之前做选择，在递归之后撤销选择

其中，全排列2用到了剪枝

전체 배열 1

class Solution {
    List> res = new LinkedList<>();
    public List> permute(int[] nums) {
        // 
        List track = new LinkedList<>();
        // 
        backtrack(nums, track);
        return res;
    }
    public void backtrack(int[] nums, List 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.remove(track.size()-1);
        }
    }
}

전체 배열 2

class Solution {
    List> res = new LinkedList<>();
    boolean[] isvisited;
    public List> permuteUnique(int[] nums) {
        List track = new LinkedList<>();
        isvisited = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, isvisited, track);
        return res;
    }
     public void backtrack(int[] nums, boolean[] isvisited, List track){
        if(track.size() == nums.length){
            res.add(new LinkedList(track));
            return;
        }
        for(int i = 0 ; i < nums.length; i++ ){
            if(isvisited[i]){
                continue;
            }
            if(i > 0 && nums[i]==nums[i-1] && isvisited[i-1]){
                continue;
            }
            
            track.add(nums[i]);
            isvisited[i] = true;
            backtrack(nums, isvisited, track);
            track.remove(track.size()-1);
            isvisited[i]= false;
        }
    }
}