当前位置:网站首页>LeetCode:39. 组合总和
LeetCode:39. 组合总和
2022-07-06 08:44:00 【Bertil】
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target 的不同组合数少于 150 个。
示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。
示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3:
输入: candidates = [2], target = 1
输出: []
提示:
- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- candidate 中的每个元素都 互不相同
- 1 <= target <= 500
解题思路
1.使用回溯(即DFS用约束条件做剪枝):首先对数组进行升序,然后定义递归函数,但须注意:数字可以被重复使用,所以每次递归,传入的起点是i
2.利用两个条件做剪枝,即递归出口:
- 满足条件,拷贝一份放入结果数组
- 剩余的目标数小于当前元素,后面的元素只会更大,直接放弃此轮
回溯和DFS,其主要的区别是,回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树
代码
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */
var combinationSum = function(candidates, target) {
const res = [];
// 升序排序
candidates.sort((a, b) => a - b);
const search = (path, target, start) => {
if (target === 0) {
// 满足条件,拷贝一份放入结果数组
res.push([...path]);
return;
}
// 注意起点为start
for (let i = start; i < candidates.length; i++) {
// 剩余的目标数小于当前元素,后面的元素只会更大,直接放弃此轮
if (target < candidates[i]) return;
path.push(candidates[i]);
// 数字可以重复,所以传入i
search(path, target - candidates[i], i);
path.pop();
}
};
search([], target, 0);
return res;
};
边栏推荐
- Screenshot in win10 system, win+prtsc save location
- 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
- The problem and possible causes of the robot's instantaneous return to the origin of the world coordinate during rviz simulation
- sublime text中conda环境中plt.show无法弹出显示图片的问题
- China polyether amine Market Forecast and investment strategy report (2022 Edition)
- Is it safe to open an account in Zheshang futures?
- China vanadium battery Market Research and future prospects report (2022 Edition)
- Visual implementation and inspection of visdom
- What is CSRF (Cross Site Request Forgery)?
- R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
猜你喜欢
The harm of game unpacking and the importance of resource encryption
vb. Net changes with the window, scales the size of the control and maintains its relative position
Roguelike游戏成破解重灾区,如何破局?
Double pointeur en langage C - - modèle classique
egg. JS getting started navigation: installation, use and learning
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
MySQL learning records 12jdbc operation transactions
Screenshot in win10 system, win+prtsc save location
Detailed explanation of heap sorting
TCP/IP协议
随机推荐
Deep analysis of C language data storage in memory
Revit secondary development Hof method calls transaction
C language double pointer -- classic question type
Charging interface docking tutorial of enterprise and micro service provider platform
Sort according to a number in a string in a column of CSV file
Trying to use is on a network resource that is unavailable
Visual implementation and inspection of visdom
Using pkgbuild:: find in R language_ Rtools check whether rtools is available and use sys The which function checks whether make exists, installs it if not, and binds R and rtools with the writelines
Process of obtaining the electronic version of academic qualifications of xuexin.com
Fairguard game reinforcement: under the upsurge of game going to sea, game security is facing new challenges
Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
【嵌入式】使用JLINK RTT打印log
To effectively improve the quality of software products, find a third-party software evaluation organization
Tcp/ip protocol
sublime text没关闭其他运行就使用CTRL+b运行另外的程序问题
What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
LeetCode:236. 二叉树的最近公共祖先
生成器参数传入参数
LeetCode:673. 最长递增子序列的个数
自动化测试框架有什么作用?上海专业第三方软件测试公司安利