LC 46 Permutations(M)

Given a collection of distinct numbers, return all possible permutations.

解题思路 采用Recursive

方法1 路是采用逐一向中间集添加元素，并将当中间集元素个数等于 nums 长度的时候，将中间集添加到结果集中，并终止该层递归

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      //依次把值放入 tempList,如果已经有，就跳过
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         //一旦有新值放入，递归循环到下一个长度
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         //删除最后的值，看能不继续加新的值
         tempList.remove(tempList.size() - 1);
      }
   }
}
Code flow
1 -> 1,2 -> 1,2,3 
     1,3 -> 1,3,2
2 -> 2,1 -> 2,1,3
     2,3 -> 2,3,1
3 -> 3,1 -> 3,1,2
     3,2 -> 3,2,1

方法2 当n=1时，数组中只有一个数a1，其全排列只有一种，即为a1

当n=2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2

当n=3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> permutations = new ArrayList<>();
   if (nums.length == 0) {
      return permutations;
   }   
   collectPermutations(nums, 0, new ArrayList<>(), permutations);
   return permutations;
}

private void collectPermutations(int[] nums, int start, List<Integer> permutation, List<List<Integer>>  permutations) {    
   if (permutation.size() == nums.length) {
      permutations.add(permutation);
      return;
   }
   for (int i = 0; i <= permutation.size(); i++) {
      // 用传进来的 排列重构一个新的临时排列
      List<Integer> newPermutation = new ArrayList<>(permutation);
      // 分别把新的nums[start] 插入 临时排列的每个位置（0， permutation.size，
      newPermutation.add(i, nums[start]);
      // 每插一个位置 递归循环到下一个长度。
      collectPermutations(nums, start + 1, newPermutation, permutations);
   }
}
code flow
1-> 2,1 -> 3,2,1 | 2,3,1 | 2,1,3
    1,2 -> 3,1,2 | 1,3,1 | 1,2,3