当前位置:网站首页>LeetCode:39. Combined sum
LeetCode:39. Combined sum
2022-07-06 08:50:00 【Bertil】
To give you one No repeating elements Array of integers for candidates And a target integer target , find candidates You can make the sum of numbers as the target number target Of all Different combinations , And return... As a list . You can press In any order Return these combinations .
candidates Medium The same Numbers can Unlimited repeat selected . If the selected number of at least one number is different , Then the two combinations are different .
For a given input , Guarantee and for target The number of different combinations of is less than 150 individual .
Example 1:
Input :candidates = [2,3,6,7], target = 7
Output :[[2,2,3],[7]]
explain :
2 and 3 Can form a set of candidates ,2 + 2 + 3 = 7 . Be careful 2 You can use it multiple times .
7 Is also a candidate , 7 = 7 .
Only these two combinations .
Example 2:
Input : candidates = [2,3,5], target = 8
Output : [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input : candidates = [2], target = 1
Output : []
Tips :
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate Every element in is Different from each other
- 1 <= target <= 500
Their thinking
1. Using backtracking ( namely DFS Prune with constraints ): First, ascending the array , Then define recursive functions , But pay attention to : Numbers can be reused , So every recursion , The starting point of incoming is i
2. Use two conditions to prune , Recursive exit :
- Meet the conditions , Copy one into the result array
- The number of remaining targets is less than the current element , The latter elements will only be larger , Abandon this round directly
Backtracking and DFS, The main difference is , The backtracking method does not retain the complete tree structure in the solution process , While depth first search records the complete search tree
Code
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */
var combinationSum = function(candidates, target) {
const res = [];
// Ascending sort
candidates.sort((a, b) => a - b);
const search = (path, target, start) => {
if (target === 0) {
// Meet the conditions , Copy one into the result array
res.push([...path]);
return;
}
// Note that the starting point is start
for (let i = start; i < candidates.length; i++) {
// The number of remaining targets is less than the current element , The latter elements will only be larger , Abandon this round directly
if (target < candidates[i]) return;
path.push(candidates[i]);
// Numbers can be repeated , So the introduction i
search(path, target - candidates[i], i);
path.pop();
}
};
search([], target, 0);
return res;
};
边栏推荐
- What is CSRF (Cross Site Request Forgery)?
- C language double pointer -- classic question type
- @Jsonbackreference and @jsonmanagedreference (solve infinite recursion caused by bidirectional references in objects)
- sublime text没关闭其他运行就使用CTRL+b运行另外的程序问题
- Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
- 广州推进儿童友好城市建设,将探索学校周边200米设安全区域
- Hutool gracefully parses URL links and obtains parameters
- MySQL uninstallation and installation methods
- Cesium draw points, lines, and faces
- Restful API design specification
猜你喜欢
Compétences en mémoire des graphiques UML
visdom可视化实现与检查介绍
多元聚类分析
ESP8266-RTOS物联网开发
sublime text没关闭其他运行就使用CTRL+b运行另外的程序问题
Charging interface docking tutorial of enterprise and micro service provider platform
Delay initialization and sealing classes
电脑清理,删除的系统文件
[embedded] print log using JLINK RTT
Swagger setting field required is mandatory
随机推荐
R language uses the principal function of psych package to perform principal component analysis on the specified data set. PCA performs data dimensionality reduction (input as correlation matrix), cus
Revit 二次开发 HOF 方式调用transaction
Navicat premium create MySQL create stored procedure
TDengine 社区问题双周精选 | 第三期
To effectively improve the quality of software products, find a third-party software evaluation organization
Revit secondary development Hof method calls transaction
Computer graduation design PHP Zhiduo online learning platform
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
Sublime text in CONDA environment plt Show cannot pop up the problem of displaying pictures
【嵌入式】Cortex M4F DSP库
Computer cleaning, deleted system files
egg. JS directory structure
生成器参数传入参数
LeetCode:剑指 Offer 42. 连续子数组的最大和
Shift Operators
同一局域网的手机和电脑相互访问,IIS设置
MYSQL卸载方法与安装方法
力扣每日一题(二)
sublime text的编写程序时的Tab和空格缩进问题
软件卸载时遇到trying to use is on a network resource that is unavailable