作者:政委锤炼_394_774 | 来源:互联网 | 2023-08-30 10:43
题目描述:给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。题目解析:回溯的过程是执行一次深度优先遍历,一条路走到底,走不通
题目描述:
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
题目解析:回溯的过程是执行一次深度优先遍历,一条路走到底,走不通的时候,返回回来,继续执行,一直这样下去,直到回到起点。
![技术分享图片](https://img6.php1.cn/3cdc5/c6c6/42f/906b146ccd4875fe.jpeg)
代码实现:注意空集也是集合的子集
将结果集扩大操作放在循环里面
public static List> subsets(int[] nums) {
List> res = new ArrayList<>();
return backTrace(0, nums, res, new ArrayList<>());
}
private static List> backTrace(int i, int[] nums, List> res, ArrayList tmp) {
if (tmp.size() == 0) {
res.add(new ArrayList<>(tmp));
}
for (int j = i; j tmp.add(nums[j]);
res.add(new ArrayList<>(tmp));
backTrace(j + 1, nums, res, tmp);
//递归结束,恢复状态
tmp.remove(tmp.size() - 1);
}
return res;
}
将结果集新增放在循环外面
class Solution {
public static List> subsets(int[] nums) {
List> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<>());
return res;
}
private static void backtrack(int i, int[] nums, List> res, ArrayList tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}