当前位置:网站首页>Leetcode刷题记录(数组)组合总和、组合总和 II
Leetcode刷题记录(数组)组合总和、组合总和 II
2022-07-07 06:28:00 【白蝶丶】
真是好久没刷题,好久没写博客了,最怪的是最近也没忙什么,秋招在即,此篇仅记录刷题过程,为以后复习做准备
一、组合总和
这道题是个典型的DFS,通过选和不选两种状态进行深搜,由于一个数可以不限次数的选取,所以在递归中,下标无需加一
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> item = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
dfs(candidates,target,item,ans,0);
return ans;
}
public void dfs(int[] candidates, int target,List<Integer> item,List<List<Integer>> ans,int index){
if(index == candidates.length){
return ;
}
if(target == 0){
ans.add(new ArrayList(item));
return ;
}
//不选
dfs(candidates,target,item,ans,index+1);
//选
if(target-candidates[index] >= 0){
item.add(candidates[index]);
dfs(candidates,target-candidates[index],item,ans,index);
item.remove(item.size()-1);
}
}
}
二、组合总和 II
这道题比上题多加了个限制,就是每一个数只能用一次,并且不能包含重复的集合
1、每一个数用一次:这个只需要在每次递归时让index++就能解决,选取了当前数,就不能在选这个数了
2、不能包含重复的集合:这个我们可以先将数组排好序,在每一层循环中只能选择一种数,例如:1 1 1 2 2 这组数,在第一层循环中如果选择了第一个1,那么就不能选择第二个1,下次选择满足条件的话就只能选择2,不然就会造成重复的问题
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> item = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(candidates);
dfs(candidates,target,item,ans,0);
return ans;
}
public void dfs(int[] candidates, int target,List<Integer> item,List<List<Integer>> ans,int index){
if(target == 0){
ans.add(new ArrayList(item));
return ;
}
for(int i = index ; i <candidates.length ; i++){
if(i!=index&&candidates[i]==candidates[i-1]){
//防止同一层循环宣选到一样的数
continue;
}
if(target - candidates[i] >= 0){
item.add(candidates[i]);
dfs(candidates,target-candidates[i],item,ans,i+1);
item.remove(item.size()-1);
}
}
}
}
边栏推荐
- Simulation volume leetcode [general] 1609 Parity tree
- OpenGL 3D graphics rendering
- Simulation volume leetcode [general] 1557 The minimum number of points that can reach all points
- LeetCode 715. Range module
- Systick滴答定时器
- Recommended by Alibaba P8, the test coverage tool - Jacobo is very practical
- RuntimeError: Calculated padded input size per channel: (1 x 1). Kernel size: (5 x 5). Kernel size c
- C语言指针(特别篇)
- Unityshader introduction essentials personal summary -- Basic chapter (I)
- GoLand set goproxy
猜你喜欢
Systick滴答定时器
寄存器地址名映射
Expérience de port série - simple réception et réception de données
2020 year end summary
LeetCode 736. Lisp 语法解析
Goldbach conjecture C language
Ppt template and material download website (pure dry goods, recommended Collection)
面板显示技术:LCD与OLED
Calf problem
[MySQL] detailed explanation of trigger content of database advanced
随机推荐
Why choose cloud native database
STM32串口寄存器库函数配置方法
Implement custom memory allocator
C语言指针(中篇)
Count the number of words in the string c language
Three updates to build applications for different types of devices | 2022 i/o key review
Required String parameter ‘XXX‘ is not present
systemd
Opencv converts 16 bit image data to 8 bits and 8 to 16
H3C vxlan configuration
RuntimeError: Calculated padded input size per channel: (1 x 1). Kernel size: (5 x 5). Kernel size c
Original collection of hardware bear (updated on June 2022)
[wechat applet: cache operation]
ChaosBlade:混沌工程简介(一)
Troublesome problem of image resizing when using typora to edit markdown to upload CSDN
PPT模板、素材下载网站(纯干货,建议收藏)
Port occupation troubleshooting
徽商期货公司评级是多少?开户安全吗?我想开户,可以吗?
【ChaosBlade:节点磁盘填充、杀节点上指定进程、挂起节点上指定进程】
Isomorphic C language