当前位置:网站首页>Leetcode 40: combined sum II
Leetcode 40: combined sum II
2022-07-07 07:53:00 【Swarford】
Ideas : to flash back ( Elements can be duplicated and cannot be checked )
The combination problem is equivalent to the subset problem ! Question combination means asking and doing tartget Subset ;
Use extra sum To record the sum of elements !sum Recorded elements and path The recorded elements are the same , After recursion ends, it is also connected with path Same withdrawal !
Elements Repeat be ① First Sort ② use i>start && nums[i]==nums[i-1]
To screen !
Be careful :
When sum Has more than target There's no need to traverse , Save money !
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) {
// If there is repetition, you should sort first !
Arrays.sort(nums);
dfs(nums,target,0);
return res;
}
void dfs(int[] nums,int target,int start){
// Termination conditions 1 : Meet the conditions to add to res
if(sum==target){
res.add(new LinkedList(path));
return;
}
// Termination conditions 2 : When sum Greater than target direct return, Otherwise, the time limit is exceeded !
if(sum>target){
return;
}
for(int i=start;i<nums.length;i++){
// choice
if(i>start && nums[i]==nums[i-1]){
continue;
}
path.add(nums[i]);
sum+=nums[i];
//
dfs(nums,target,i+1);
// revoke
path.removeLast();
sum-=nums[i];
}
}
}
边栏推荐
- Linux server development, MySQL stored procedures, functions and triggers
- Detailed explanation of uboot image generation process of Hisilicon chip (hi3516dv300)
- [Stanford Jiwang cs144 project] lab3: tcpsender
- buuctf misc USB
- 【webrtc】m98 screen和window采集
- Explore Cassandra's decentralized distributed architecture
- 自定义类加载器加载网络Class
- misc ez_usb
- Value sequence (subsequence contribution problem)
- ASEMI整流桥RS210参数,RS210规格,RS210封装
猜你喜欢
The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
After the interview, the interviewer roast in the circle of friends
[UTCTF2020]file header
有 Docker 谁还在自己本地安装 Mysql ?
2022-07-06: will the following go language codes be panic? A: Meeting; B: No. package main import “C“ func main() { var ch chan struct
快速使用 Jacoco 代码覆盖率统计
《动手学深度学习》(四) -- 卷积神经网络 CNN
ASEMI整流桥RS210参数,RS210规格,RS210封装
@component(““)
Mysql高低版本切换需要修改的配置5-8(此处以aicode为例)
随机推荐
What are the positions of communication equipment manufacturers?
Few-Shot Learning && Meta Learning:小样本学习原理和Siamese网络结构(一)
大视频文件的缓冲播放原理以及实现
paddlepaddle 29 无模型定义代码下动态修改网络结构(relu变prelu,conv2d变conv3d,2d语义分割模型改为3d语义分割模型)
Button wizard script learning - about tmall grabbing red envelopes
Cnopendata American Golden Globe Award winning data
2022制冷与空调设备运行操作复训题库及答案
2022年茶艺师(中级)考试试题及模拟考试
Shell 脚本的替换功能实现
Linux server development, MySQL process control statement
ASEMI整流桥RS210参数,RS210规格,RS210封装
PHP exports millions of data
Gslx680 touch screen driver source code analysis (gslx680. C)
Leetcode 43 String multiplication (2022.02.12)
微信小程序中使用wx.showToast()进行界面交互
[Stanford Jiwang cs144 project] lab3: tcpsender
Why should we understand the trend of spot gold?
2022焊工(初级)判断题及在线模拟考试
After the interview, the interviewer roast in the circle of friends
Pytest + allure + Jenkins Environment - - achèvement du remplissage de la fosse