今天在力扣上做了一个关于组合总和的题目，题目如下：
我实现的代码如下：
点击查看代码
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> perList = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtrace(candidates, target, 0);
return result;
}
private void backtrace(int[] candidates, int target, int index) {
if (target == 0) {
result.add(perList);
return;
} else if (target < 0){
return;
}
for (int i = index; i < candidates.length; i++) {
perList.add(candidates[i]);
target -= candidates[i];
backtrace(candidates, target, i);
target += candidates[i];
perList.remove(perList.size()-1);
}
}
}
测试用例如下所示：
可以看到'result.size()=3'，因此该代码是可以遍历到每一个候选组合的，但是传出的result数组却包含了三个空数组。然后我用debug调试了一下，发现每次更新perList数组，都会连带着更新result，从而删除result中的所有元素。
上网搜了一下，ArrayList对象直接赋值给另一个ArrayList对象属于浅拷贝。浅copy就是返回元素一样的ArrayList，但是元素本身并没有copy，如果原来元素的内容改变了，两个ArrayList内容都会随着改变（两部分公用元素）。深copy是指复制后两部分完全没有交集，各自有各自的元素。
改为下面代码，运行通过。
点击查看代码
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> perList = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtrace(candidates, target, 0);
return result;
}
private void backtrace(int[] candidates, int target, int index) {
if (target == 0) {
//新建对象拷贝
result.add(new ArrayList<>(perList));
return;
} else if (target < 0){
return;
}
for (int i = index; i < candidates.length; i++) {
perList.add(candidates[i]);
target -= candidates[i];
backtrace(candidates, target, i);
target += candidates[i];
perList.remove(perList.size()-1);
}
}
}