当前位置:网站首页>Leetcode question brushing record (array) combination sum, combination sum II
Leetcode question brushing record (array) combination sum, combination sum II
2022-07-07 09:04:00 【White butterfly】
I haven't scratched the question for a long time , I haven't written a blog for a long time , The strangest thing is that I haven't been busy lately , Autumn moves are just around the corner , This article only records the process of question brushing , Prepare for future review
One 、 Combinatorial summation
This problem is a typical DFS, Search deeply by selecting and not selecting two states , Because a number can be selected unlimited times , So in recursion , There is no need to add one to the subscript
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 ;
}
// No election
dfs(candidates,target,item,ans,index+1);
// choose
if(target-candidates[index] >= 0){
item.add(candidates[index]);
dfs(candidates,target-candidates[index],item,ans,index);
item.remove(item.size()-1);
}
}
}
Two 、 Combinatorial summation II
This question is more restrictive than the previous one , Each number can only be used once , And cannot contain duplicate sets
1、 Use each number once : This only needs to let index++ It can be solved , The current number is selected , You can't choose this number
2、 Cannot contain duplicate sets : We can arrange the array first , In each layer of the loop, only A number , for example :1 1 1 2 2 This group of numbers , If the first one is selected in the first layer of loop 1, Then you can't choose the second 1, The next time you choose to meet the conditions, you can only choose 2, Otherwise, it will cause repeated problems
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]){
// Prevent the same layer from circulating and selecting the same number
continue;
}
if(target - candidates[i] >= 0){
item.add(candidates[i]);
dfs(candidates,target-candidates[i],item,ans,i+1);
item.remove(item.size()-1);
}
}
}
}
边栏推荐
- Esp32-ulp coprocessor low power mode RTC GPIO interrupt wake up
- Unity Shader入门精要初级篇(一)-- 基础光照笔记
- Systick滴答定时器
- 最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
- 硬件大熊原创合集(2022/06更新)
- Calculation s=1+12+123+1234+12345 C language
- cmake命令行使用
- Lenovo hybrid cloud Lenovo xcloud: 4 major product lines +it service portal
- Cmake command line use
- Goldbach conjecture C language
猜你喜欢
Calf problem
Nanjing commercial housing sales enabled electronic contracts, and Junzi sign assisted in the online signing and filing of housing transactions
UnityShader入门精要个人总结--基础篇(一)
2020 year end summary
PMP certificate preparation experience sharing
面试题:高速PCB一般布局、布线原则
STM32串口寄存器库函数配置方法
[istio introduction, architecture, components]
串口實驗——簡單數據收發
Oracle makes it clear at one time that a field with multiple separators will be split into multiple rows, and then multiple rows and columns. Multiple separators will be split into multiple rows, and
随机推荐
NVIC中断优先级管理
Unity shader beginner's Essentials (I) -- basic lighting notes
Original collection of hardware bear (updated on June 2022)
Greenplum 6.x build_ install
Uniapp wechat applet monitoring network
Several common database connection methods
【ChaosBlade:根据标签删除POD、Pod 域名访问异常场景、Pod 文件系统 I/O 故障场景】
On December 8th, 2020, the memory of marketing MRC application suddenly increased, resulting in system oom
How to realize sliding operation component in fast application
channel. Detailed explanation of queuedeclare parameters
[chaosblade: node disk filling, killing the specified process on the node, suspending the specified process on the node]
JVM 垃圾回收 详细学习笔记(二)
【Istio Network CRD VirtualService、Envoyfilter】
Reading notes of pyramid principle
阿里p8手把手教你,自动化测试应该如何实现多线程?赶紧码住
Isomorphic C language
Implement custom memory allocator
9c09730c0eea36d495c3ff6efe3708d8
Mountaineering team (DFS)
The longest ascending subsequence model acwing 1017 Strange thief Kidd's glider