面试算法79:所有子集
2024-01-02 12:31:40
题目
输入一个不含重复数字的数据集合,请找出它的所有子集。例如,数据集合[1,2]有4个子集,分别是[]、[1]、[2]和[1,2]。
分析
如果集合中包含n个元素,那么生成子集可以分为n步,每一步从集合中取出一个数字,此时面临两个选择,将该数字添加到子集中或不将该数字添加到子集中。生成一个子集可以分为若干步,并且每一步都面临若干选择,这正是应用回溯法的典型场景。
解
public class Test {
public static void main(String[] args) {
int[] nums = {1, 2};
List<List<Integer>> result = subsets(nums);
for (List<Integer> item : result) {
System.out.println(item);
}
}
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new LinkedList<>();
if (nums.length == 0) {
return result;
}
helper(nums, 0, new LinkedList<Integer>(), result);
return result;
}
private static void helper(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> result) {
if (index == nums.length) {
result.add(new LinkedList<>(subset));
}
else if (index < nums.length) {
helper(nums, index + 1, subset, result);// 直接不添加元素
subset.add(nums[index]);// 添加元素
helper(nums, index + 1, subset, result);
// 等递归函数执行完成之后,函数helper也执行完成,接下来将回到前一个数字的函数调用处继续执行。那么此时将回溯到父节点,以便尝试父节点的其他选项。
// 在回溯到父节点之前,应该清除已经对子集状态进行的修改。此前在子集subset中添加了一个数字,此时应该将它删除。
subset.removeLast();
}
}
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135336396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!