8. ＜ tag backtracking and full arrangement ＞ lt.46 Full Permutation + lt.47 Full arrangement II

lt.46. Full Permutation

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]

class Solution {
    
    List<List<Integer>> lists = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
    
        // Record the path of leaf nodes list
        List<Integer> path = new ArrayList<>();

        // The record is to traverse a path ,  Whether the nodes on this path are used 
        boolean[] used = new boolean[nums.length]; 

        backTracking(nums, path, used);

        return lists;
    }
    
    //1.  Recursive function ,  Trace back the combined path of all nodes . 
    // Parameters : path Is to record each sub path , used Mark whether a node is used 
    public void backTracking(int[] nums, List<Integer> path, boolean[] used){
    
        //2.  Recursion end condition 
        // path The path recorded in is equal to the length of the selection list 
         //nums The array is used for choices such as 1,2,3/ path Only when the leaf node is recorded will it be equal to nums The length of 
        if(path.size() == nums.length){
     
            lists.add(new ArrayList(path)); //?????
            return;
        }  

        // The process of backtracking , 
        // for Loop breadth traversal 
        //  Backtracking is responsible for traversing a path ,  Then return to the initial position 
        for(int i = 0; i < nums.length; i++){
    
            // The current path node is already in use 

}
            if(used[i] == true)continue;

            path.add(nums[i]);
            used[i] = true;

            backTracking(nums, path, used);

            path.remove(path.size() - 1); /// ????
            used[i] = false;

        }
    }
}

lt.47. Full Permutation II

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]

class Solution {
    
    List<List<Integer>> lists = new ArrayList<>();
     List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
    
        // Record the path of leaf nodes list
       

        // The record is to traverse a path ,  Whether the nodes on this path are used 
        boolean[] used = new boolean[nums.length]; 

        Arrays.sort(nums);
        backTracking(nums, used);

        return lists;
    }
    
    //1.  Recursive function ,  Trace back the combined path of all nodes . 
    // Parameters : path Is to record each sub path , used Mark whether a node is used 
    public void backTracking(int[] nums, boolean[] used){
    
        //2.  Recursion end condition 
        // path The path recorded in is equal to the length of the selection list 
         //nums The array is used for choices such as 1,2,3/ path Only when the leaf node is recorded will it be equal to nums The length of 
        if(path.size() == nums.length){
     
            lists.add(new ArrayList(path)); //?????
            return;
        }  

        // The process of backtracking , 
        // for Loop breadth traversal 
        //  Backtracking is responsible for traversing a path ,  Then return to the initial position 
        for(int i = 0; i < nums.length; i++){
    
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    
    continue;
}
            if(used[i] == false){
    
      

            path.add(nums[i]);
            used[i] = true;

            backTracking(nums, used);

            path.remove(path.size() - 1); /// ????
            used[i] = false;
            }

        }
    }
}