一、题目描述
======
子集
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例1 输入：nums = [1,2,3] 输出：
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例2 输入：nums = [0] 输出：
[[],[0]]
二、思路分析
======
- 相信大多数人想到的都是递归实现。既然是子集我们里面肯定有自己的一个个数。在每次递归待携带者一个自己长度去填充子集就可以填补出内容了。
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets2(int[] nums) {
diguiWithLenght(0, nums);
return ans;
}
public void diguiWithLenght(int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
t.add(nums[cur]);
diguiWithLenght(cur 1, nums);
t.remove(t.size() - 1);
diguiWithLenght(cur 1, nums);
}- 只需要在递归中出现回退是将最后数据删除，这样就会回溯到上一条路继续递归。这种解法理解有点难度。今天笔者带你通过另外一种思路打开这道题
滚雪球
- 笔者的实现是通过滚雪球方式将结果集越滚越大最终达到结果。首先我们知道空数组也是一个子集 。所以我们默认添加空数组
- 然后对原数组
[1,2,3]进行逐个遍历将里面的元素单个逐个添加到新的复制数组中，这样说可能有点抽象下面我们通过一幅图理解下 - 当我们处理2这个节点时，将已有的结果集整体复制一遍。在新复制的节点集中诶个添加2
- 一直重复这个操作，知道最后一个元素添加结束。最后这个结果集就是我们所有的子集 。 笔者贴心的制作一套动画赶快观看吧。动画动画动画！！！
三、AC 代码
=======
代码语言：java复制public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> resultList = new ArrayList<>();
resultList.add(new ArrayList<>());
for (int num : nums) {
int length = resultList.size();
for (int i = 0; i < length; i ) {
List<Integer> subResult = resultList.get(i);
List<Integer> temList = new ArrayList<>();
temList.addAll(subResult);
temList.add(num);
resultList.add(temList);
}
}
return resultList;
}- 经过对比滚雪球虽然理解上方便点。但是内存上有点大。仅供参考。因为里面借助了一个额外的数组。
- 为什么需要这个额外的数组呢？因为数组在java中会通过引用传递。如果我们仅仅将引用对象赋值过去的话，这样我们就会污染了原内容。
四、总结
====
- 滚雪球又称作扩展法。基于一个基础数据不断的对数据进行赋值增加内容。最终达到我们子集的集合
我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
