当前位置: 首页> 科技> 名企 > 专业宣传片制作拍摄公司_推广简短吸引人的话_上海哪家优化公司好_拓客软件哪个好用

专业宣传片制作拍摄公司_推广简短吸引人的话_上海哪家优化公司好_拓客软件哪个好用

时间:2025/7/11 15:27:31来源:https://blog.csdn.net/2302_81116822/article/details/146888713 浏览次数:1次
专业宣传片制作拍摄公司_推广简短吸引人的话_上海哪家优化公司好_拓客软件哪个好用

问题描述

给定一个不含重复元素的整数数组 nums,返回其所有可能的子集(幂集)。

示例

输入: nums = [1,2,3]

输出:

[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]

解法:回溯算法

回溯是一种 暴力搜索 方法,它通过 枚举所有可能的解 来解决问题。回溯算法的关键在于:

  1. 选择:在当前状态下选择一个可行的元素加入子集中。

  2. 递归:基于当前选择,递归探索剩余元素的子集。

  3. 回溯:撤销上一步选择,尝试其他可能。

代码实现

import java.util.*;class Solution {public List<List<Integer>> ans = new ArrayList<>();public List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return ans;}public void dfs(int[] nums, int i) {ans.add(new ArrayList<>(path)); // 记录当前子集for (int j = i; j < nums.length; j++) {path.add(nums[j]);  // 选择元素 nums[j]dfs(nums, j + 1);   // 递归处理剩余元素path.remove(path.size() - 1);  // 回溯,撤销选择}}
}

代码解析

1. 变量定义

public List<List<Integer>> ans = new ArrayList<>();
public List<Integer> path = new ArrayList<>();
  • ans:存储所有可能的子集。

  • path:存储当前正在构造的子集。

2. 递归函数

public void dfs(int[] nums, int i) {ans.add(new ArrayList<>(path)); // 记录当前子集for (int j = i; j < nums.length; j++) {path.add(nums[j]);  // 选择 nums[j]dfs(nums, j + 1);   // 递归path.remove(path.size() - 1);  // 回溯}
}
核心逻辑
  1. 存储当前子集:进入递归时,首先将 path 加入 ans,确保所有子集都被记录。

  2. 遍历所有可能的选择

    • ji 开始,确保所有元素只能被选择一次,避免重复。

    • 选择 nums[j] 后,递归 dfs(nums, j+1) 处理剩余元素。

  3. 回溯:递归结束后,撤销上一步的选择(path.remove()),探索其他可能。

递归执行过程

假设 nums = [1,2,3],其递归树如下:

dfs(0, [])  --> 添加 []├── dfs(1, [1])  --> 添加 [1]│   ├── dfs(2, [1,2])  --> 添加 [1,2]│   │   ├── dfs(3, [1,2,3])  --> 添加 [1,2,3]│   │   └── 回溯到 [1,2]│   ├── dfs(3, [1,3])  --> 添加 [1,3]│   └── 回溯到 [1]├── dfs(2, [2])  --> 添加 [2]│   ├── dfs(3, [2,3])  --> 添加 [2,3]│   └── 回溯到 [2]├── dfs(3, [3])  --> 添加 [3]└── 回溯到 []

最终 ans 存储的子集为:

[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]

时间复杂度分析

  • 每个元素可以 选或不选,因此总共有 2^n 种可能的子集。

  • 递归深度为 n,每次递归的操作为 O(1)

  • 总时间复杂度:O(2^n * n),近似 O(2^n),指数级复杂度。

总结

  1. 回溯思路

    • 递归枚举所有可能的子集。

    • 先将 path 存入 ans,然后继续选择下一个元素。

    • 递归结束后 回溯,撤销上一步的选择。

  2. 避免重复

    • ji 开始,保证每个元素只被选一次,避免重复子集。

  3. 适用场景

    • 由于时间复杂度为 O(2^n),适用于 n ≤ 20 的情况。

这个方法是解决子集问题的经典方式,希望对你有所帮助!

关键字:专业宣传片制作拍摄公司_推广简短吸引人的话_上海哪家优化公司好_拓客软件哪个好用

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: