78. 子集 - 力扣（LeetCode）
class Solution {private List<Integer> path=new ArrayList<>();private List<List<Integer>> ans=new ArrayList<>();private int []nums; public List<List<Integer>> subsets(int[] nums) {this.nums=nums;dfs(0);return ans;}public void dfs(int i){if(i==nums.length){ans.add(new ArrayList(path));return ;}dfs(i+1);path.add(nums[i]);dfs(i+1);path.remove(path.size()-1);}
}在 Java 中，List 是对象，直接传递 path 时，传递的是对象的引用（即内存地址），而不是当前路径的“快照”。这会导致所有添加到 ans 中的结果实际上都指向同一个 path 对象。当后续回溯修改 path 时（比如 path.remove(...)），所有已添加到 ans 中的结果也会跟着被修改！最终你会看到 ans 中的每个子集都是空的，因为它们最终都指向同一个被清空了的 path。
通过一个具体例子理解问题：
假设 nums = [1,2,3]，递归过程如下：
-
当递归到最深层（
i == 3）时，path为空，此时ans.add(path)。此时ans中的第一个元素是path的引用。 -
回溯到上一层，
path.add(3)，然后再次递归到i=3，此时path = [3]，ans.add(path)。此时ans中有两个元素，但它们都指向同一个path对象。 -
继续回溯，
path.remove(3)，此时path变回空列表，而ans中已有的两个元素（引用）也会看到这个变化，结果都变成空列表！
最终 ans 中的所有子集会因为共享同一个 path 对象而全部被清空。
恢复现场： 在递归到某一“叶子节点”（非最后一个叶子）时，答案需要向上返回，而此时还有其他的子树（与前述节点不在同一子树）未被递归到，又由于path为全局变量。若直接返回，会将本不属于该子树的答案带上去，故需要恢复现场。 恢复现场的方式为：在递归完成后 dfs(i+1); 后，进行与“当前操作”相反的操作，“反当前操作”。
131. 分割回文串 - 力扣（LeetCode）
这题其实还是有点不理解 先写个注释 mark一下
class Solution {private List<String> path=new ArrayList<>();private List<List<String>>ans=new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s=s;dfs(0,0);return ans;}public void dfs(int i,int start){// i表示当前选择的s的下标 当i等于s的长度时 说明已经分割完毕if(i==s.length()){// 将path的副本加入到答案中ans.add(new ArrayList<>(path));// 回溯继续选择其他的可能return;}// 这里注意很巧妙的判断 一开始写的是i==s.length()-1想要判断当i=size-1的时候必须分割// 但是其实应该写的i<size-1 这样就包含了上面的情况 并且按照之前的思路进行递归 可以选也可以不选if(i<s.length()-1){dfs(i+1,start);}// 选择： 首先选择的前提是回文字符串 因此传入检查一下if(check(start,i)){// 如果符合条件就使用substring加入path.add(s.substring(start,i+1));// 继续递归 选择s字符串中下标为i+1的 并且传入上一轮遍历完 start应该在的位置i+1dfs(i+1,i+1);//恢复现场path.remove(path.size()-1);}}public boolean check(int left ,int right){while(left<right){if(s.charAt(left++)!=s.charAt(right--))return false;}return true;}
}
