Problem: 46. 全排列

复杂度

时间复杂度: $O(n\times n!)$

空间复杂度: $O(n)$

Code

class Solution{static int N = 10, n;static List<List<Integer>> ans;static int[] a;static boolean[] st = new boolean[N];public static List<List<Integer>> permute(int[] nums){ans = new ArrayList<>();n = nums.length;a = nums;dfs(new ArrayList<Integer>());
//		System.out.println(System.identityHashCode(ans));return ans;}private static void dfs(ArrayList<Integer> list){if (list.size() == n){
//			System.out.println("方法内部" + System.identityHashCode(ans));
//			错误示例
//			ans.add(list); //这里的 list 是局部变量，每次调用完就会释放内存了，导致 ans 里边加的都是 空Listans.add(new ArrayList<>(list));return;}for (int i = 0; i < n; i++){if (!st[i]){list.add(a[i]);st[i] = true;dfs(list);
//				恢复现场st[i] = false;list.remove(list.size() - 1);}}}
}