46. 全排列

image.png

思路： 肯定是回溯算法，当递归深度 == 数组长度时，说明所有数字都已经使用完了。但是需要加一个used数组，表示当前位置的数字已经使用过，避免出现重复数据

  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  4.         List<List<Integer>> res =  new ArrayList<>();
  5.         boolean[] used = new boolean[nums.length];
  6.         recall(nums,0,res , new ArrayList<>(),used);
  7.         return res;
  8.     }
  11.     public void recall(int[] nums ,int dept , List<List<Integer>> res , List<Integer> arr , boolean[]used){
  12.         if(dept == nums.length){
  13.             res.add(new ArrayList(arr));
  14.         }
  15.         for(int i = 0 ;i < nums.length ; i++){
  16.             if(!used[i]){
  17.                 arr.add(nums[i]);
  18.                 used[i] = true ;
  19.                 recall(nums,dept+1 , res , arr , used);
  20.                 used[i] = false;
  21.                 arr.remove(arr.size() -1);
  22.             }
  23.         }
  24.     }
  26. }