当前位置:网站首页>LeetCode 78:子集
LeetCode 78:子集
2022-07-06 06:55:00 【斯沃福德】
链接
题目:
思路:回溯(无重复元素不可复选)
回溯框架:
此题是形式一: 无重复元素不可复选,写回溯算法的时候,for就要从start开始,而不是从0开始! 即(2,1)和(1,2)是一个结果,故不能复选。
用start来保证每次递归时遍历数组后面未遍历到的数,而不会重复遍历前面的数
最后strat超过数组个数即为终止条件!
注意:
子集问题中,每个节点都是子集 !
需要在递归的【前序位置】将path添加到res !而不是到叶子节点才添加到res !
空集 [ ] 也算子集
Java实现:
class Solution {
List<List<Integer>> res=new LinkedList<>();
LinkedList<Integer> path=new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
if(nums==null){
return new List<List<Integer>>;
}
dfs(nums,0);
return res;
}
void dfs(int[] nums,int start){
//用start来保证每次递归时遍历数组后面的数,而不会重复遍历前面的数,
//最后strat超过数组个数即为终止条件!
// 空集[]也算子集
res.add(new LinkedList(path)); // 每个节点都是子集 !而不是到叶子节点才添加到res !
for(int i=start;i<nums.length;i++){
//递归前选择
path.add(nums[i]);
//递归,i+1确保数组中元素不被重复使用
dfs(nums,i+1);
//递归后撤销
path.removeLast();
}
}
}
边栏推荐
- Apache DolphinScheduler源码分析(超详细)
- L'Ia dans les nuages rend la recherche géoscientifique plus facile
- 从autojs到冰狐智能辅助的心里历程
- A method to measure the similarity of time series: from Euclidean distance to DTW and its variants
- 【Hot100】739. 每日温度
- After working for 10 years, I changed to a programmer. Now I'm 35 + years old and I'm not anxious
- Bitcoinwin (BCW): 借贷平台Celsius隐瞒亏损3.5万枚ETH 或资不抵债
- 成功解决AttributeError: Can only use .cat accessor with a ‘category‘ dtype
- The difference between get and post request types
- Redis Foundation
猜你喜欢
19. Actual memory management of segment page combination
Simple use of MySQL database: add, delete, modify and query
Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
LeetCode - 152 乘积最大子数组
【刷题】怎么样才能正确的迎接面试?
SAP SD发货流程中托盘的管理
Visitor tweets about how you can layout the metauniverse
基于购买行为数据对超市顾客进行市场细分(RFM模型)
Reflex WMS medium level series 3: display shipped replaceable groups
[advanced software testing step 1] basic knowledge of automated testing
随机推荐
mysql的基础命令
Refer to how customer push e-commerce does content operation
PCL实现选框裁剪点云
Proteus -- Serial Communication parity flag mode
Fedora/rehl installation semanage
漏了监控:Zabbix对Eureka instance状态监控
Market segmentation of supermarket customers based on purchase behavior data (RFM model)
Bitcoinwin (BCW): 借贷平台Celsius隐瞒亏损3.5万枚ETH 或资不抵债
Latex文字加颜色的三种办法
C语言_双创建、前插,尾插,遍历,删除
[brush questions] how can we correctly meet the interview?
Pallet management in SAP SD delivery process
雲上有AI,讓地球科學研究更省力
[unity] how to export FBX in untiy
LeetCode每日一题(971. Flip Binary Tree To Match Preorder Traversal)
Database basics exercise part 2
Blue Bridge Cup zero Foundation National Championship - day 20
Apache DolphinScheduler源码分析(超详细)
AttributeError: Can‘t get attribute ‘SPPF‘ on <module ‘models. common‘ from ‘/home/yolov5/models/comm
Classification des verbes reconstruits grammaticalement - - English Rabbit Learning notes (2)