大庆市建设大厦网站盐都建设局网站

刷题刷到LeetCode回溯DFS的算法题39题的时候,碰见一个Arraylist里面的bug,其中dfs函数里面的第一个if判断里面的语句

paths.add(path);
path.clear();

其中path是添加了path,但是添加之后path.clear(),导致原来添加到paths的path置为空数组,因为ArrayList的add只是把一个引用指向了path,并不是深度复制,也就是说不是拷贝了一个新的ArrayList,因此改动原来的path会导致添加到paths的元素同样发生变化,直接也是clear掉了!

package org.example.SolutionTest3;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int n=candidates.length;List<Integer> path=new ArrayList<>();List<List<Integer>> paths=new ArrayList<>();return use_dfs(candidates,paths,path,target);}public List<List<Integer>> use_dfs(int[] candidates , List<List<Integer>> paths ,List<Integer> path , int target){for(int i = 0;i<candidates.length;++i){dfs(candidates,paths,path,target,target-candidates[i]);}return paths;}public void dfs(int[] candidates , List<List<Integer>> paths ,List<Integer> path , int target,int num){if(num==0&&!path.isEmpty()){System.out.println("path = " + path);paths.add(path);path.clear();//path=new ArrayList<>();return;}else if(num<0&&!path.isEmpty()){path.remove(path.size()-1);return;}for( int i = 0 ; i<candidates.length;++i){int next_num = num-candidates[i];if(next_num<0){continue;}path.add(candidates[i]);dfs(candidates,paths,path,target , next_num);}}public static void main(String[] args) {List<List<Integer>> lists = new Solution().combinationSum(new int[]{2, 3, 6, 7},7);System.out.println(lists);}
}