下面的代码在编写的过程中出现了问题,查了很久,最终解决了,突然感觉好菜啊!
涉及的知识点:递归,java引用类型
/**
* 功能:求解所有集合的子集的算法实现,递归实现
*/
import java.util.ArrayList;
import java.util.List;
public class SetSons {
public static void main(String[] args) {
int[] nums = {1, 2, 3}; // 这是你的数组
List<List<Integer>> subsets = new ArrayList<>();
findSubsets(nums, 0, subsets, new ArrayList<>());
for (List<Integer> subset : subsets) {
System.out.println(subset);
}
}
private static void findSubsets(int[] nums, int start, List<List<Integer>> subsets, List<Integer> current) {
//subsets.add(new ArrayList<>(current)); // 添加当前子集的副本到结果集,刚开始的错误就是这个地方
//假如把刚才的代码语句换成下面这个,结果就会完全不一样
subsets.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
current.add(nums[i]); // 选择当前元素
findSubsets(nums, i + 1, subsets, current); // 递归选择下一个元素
current.remove(current.size() - 1); // 回溯,移除当前元素
}
}
}
解释下原因:current是ArrayList类型,也是属于引用类型,在递归过程中,current是在不断变化的,subsets.add(new ArrayList<>(current));就是将current的引用加入到目标list中。不使用副本的情况下造成了最终的子集全部为空集(回溯的原因)。递归结束后,currentList 将是一个空列表(因为它被回溯到了初始状态)。因此,list 中的所有子集都会变成空列表,因为它们都是同一个空的 currentList 的引用。
标签:错误,subsets,遇到,补充,ArrayList,nums,List,current,new From: https://blog.csdn.net/yf3241610146/article/details/143457218