题解 | JAVA 递归 #没有重复项数字的全排列# [P3]

就暴力递归 + 回溯(省空间)
每次递归, 从小到大(所以一上来要对num进行排序)遍历待选的数,
选到的数从remain中删除，并插入perm中。

O(n!) O(n!)

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
      // sort just to insure output in alphabet order
      Arrays.sort(num);
      // copy sorted nums to remain
      ArrayList<Integer> remain = new ArrayList<>();
      for (int n : num) remain.add(n); 
      
      permuteRec(remain, new ArrayList<>());
      return ans;
    }
  
    public void permuteRec(ArrayList<Integer> remain, ArrayList<Integer> perm) {
      // base case, i.e. no remaining elem
      if (remain.isEmpty()) {
        // 存答案时必须存copy, 不然之后的回溯会overwrite存入的答案。
        ans.add(new ArrayList<>(perm));
        return;
      }
      
      for (int i = 0; i < remain.size(); i++) {
        Integer a = remain.remove(i);
        perm.add(a);
        permuteRec(remain, perm);
        
        // 复原 (a.k.a 回溯)
        remain.add(i, a);
        perm.remove(perm.size()-1);
      }
    }
}