当前位置:网站首页>LeetCode 40:组合总和 II
LeetCode 40:组合总和 II
2022-07-07 04:27:00 【斯沃福德】
思路:回溯(元素可重不可复选)
组合问题和子集问题等价!问组合也就是问和为tartget的子集;
使用额外的sum来记录元素的和!sum记录的元素和path记录的元素相同,在递归到头后也和path一样撤回!
元素有重复则① 先排序 ②用 i>start && nums[i]==nums[i-1]
来筛选!
注意:
当sum已经超过target 就不需要遍历了, 节省开销!
class Solution {
List<List<Integer>> res=new LinkedList<>();
LinkedList<Integer> path=new LinkedList<>();
int sum=0;
public List<List<Integer>> combinationSum2(int[] nums, int target) {
//有重复要先排序 !
Arrays.sort(nums);
dfs(nums,target,0);
return res;
}
void dfs(int[] nums,int target,int start){
//终止条件1 :满足条件添加到res
if(sum==target){
res.add(new LinkedList(path));
return;
}
//终止条件2 :当sum大于target直接return,不然超出时间限制!
if(sum>target){
return;
}
for(int i=start;i<nums.length;i++){
//选择
if(i>start && nums[i]==nums[i-1]){
continue;
}
path.add(nums[i]);
sum+=nums[i];
//
dfs(nums,target,i+1);
//撤销
path.removeLast();
sum-=nums[i];
}
}
}
边栏推荐
- A concurrent rule verification implementation
- ASEMI整流桥RS210参数,RS210规格,RS210封装
- IO流 file
- Info | webrtc M97 update
- Leetcode-206. Reverse Linked List
- buuctf misc USB
- 1140_ SiCp learning notes_ Use Newton's method to solve the square root
- leetcode:105. Constructing binary trees from preorder and inorder traversal sequences
- The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
- 【经验分享】如何为visio扩展云服务图标
猜你喜欢
Flutter riverpod is comprehensively and deeply analyzed. Why is it officially recommended?
4、 High performance go language release optimization and landing practice youth training camp notes
Few-Shot Learning && Meta Learning:小样本学习原理和Siamese网络结构(一)
[2022 ACTF]web题目复现
[guess-ctf2019] fake compressed packets
[Linux] process control and parent-child processes
The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
图解GPT3的工作原理
nacos
Why should we understand the trend of spot gold?
随机推荐
[webrtc] m98 Screen and Window Collection
English translation is too difficult? I wrote two translation scripts with crawler in a rage
Regular e-commerce problems part1
[cloud native] how to give full play to memory advantage of memory database
《动手学深度学习》(四) -- 卷积神经网络 CNN
JSON introduction and JS parsing JSON
探索Cassandra的去中心化分布式架构
idea添加类注释模板和方法模板
自定义类加载器加载网络Class
leetcode:105. 从前序与中序遍历序列构造二叉树
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
[webrtc] M98 screen and window acquisition
【Unity】物体做圆周运动的几个思路
Pytest + allure + Jenkins Environment - - achèvement du remplissage de la fosse
面试结束后,被面试官在朋友圈吐槽了......
MobaXterm
1142_ SiCp learning notes_ Functions and processes created by functions_ Linear recursion and iteration
buuctf misc USB
JS plot flot application - simple curve
Weibo publishing cases