力扣46全排列，78子集（回溯）

全排列

• List path = Arrays.asList(new Integer[n]); 创造一个定长的 List 列表，不能最列表进行增删，只能进行修改，对这个 path 也是使用 set（i，nums[i]), 对某个位置的值进行修改。 并且对 List 中的值进行修改，那么原来的 Integer[n] 中的值也会改变
• ans.add(new ArrayList<>(path));在添加 path 的时候一定要 new ArrayList 创建一个新对象，这个属于浅拷贝，否则如果直接 add(path) 就属于深拷贝，所有添加到 ans 的引用都会指向一个 path 共同的引用，每一次对 path 进行修改， ans中的值也会随之更改
• path 在这里设置的是定长情况每次直接覆盖就可以了，否则就需要 path.removeLast(); 把最后一个添加的删除，恢复现场

class Solution {public List<List<Integer>> permute(int[] nums) {int n = nums.length;List<Integer> path = Arrays.asList(new Integer[n]);List<List<Integer>> ans = new ArrayList<>();boolean[] onPath = new boolean[n];dfs(0, nums, ans, path, onPath);return ans;}private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) {if (i == nums.length) {ans.add(new ArrayList<>(path));return ;}for (int j = 0; j < nums.length; j++) {if (!onPath[j]) {path.set(i, nums[j]);onPath[j] = true;dfs(i + 1, nums, ans, path, onPath);onPath[j] = false;}}}
}

子集

class Solution {public List<List<Integer>> subsets(int[] nums) {int n = nums.length;List<Integer> path = new ArrayList<>();List<List<Integer>> ans = new ArrayList<>();dfs(0, ans, path, nums);return ans;}private void dfs(int i, List<List<Integer>> ans, List<Integer> path, int[] nums) {if (i == nums.length) {ans.add(new ArrayList<>(path));return ;}dfs(i + 1, ans, path, nums);path.add(nums[i]);dfs(i + 1, ans, path, nums);path.removeLast();}
}