39. Combination Sum
39 sum combination
2023-09-11 14:22:45 时间
Given a set of candidate numbers (candidates
) (without duplicates) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sums to target
.
The same repeated number may be chosen from candidates
unlimited number of times.
Note:
- All numbers (including
target
) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates =[2,3,6,7],
target =7
, A solution set is: [ [7], [2,2,3] ]
Example 2:
Input: candidates = [2,3,5],
target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
AC code:
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res; vector<int> combination; sort(candidates.begin(), candidates.end()); backtracking(candidates, res, combination, target, 0); return res; } void backtracking(vector<int>& candidates, vector<vector<int>>& res, vector<int>& combination, int target, int begin) { if (!target) { res.push_back(combination); return; } for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) { combination.push_back(candidates[i]); backtracking(candidates, res, combination, target-candidates[i], i); combination.pop_back(); } } };
Runtime: 12 ms, faster than 61.39% of C++ online submissions for Combination Sum.
回溯法(英语:backtracking)是暴力搜索法中的一种。
对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,我们逐步构造更多的候选解,并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解,转而测试其他的部分候选解)。
在经典的教科书中,八皇后问题展示了回溯法的用例。(八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布,使得没有一个皇后能攻击到另外一个。)
回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
- 找到一个可能存在的正确的答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
相关文章
- python ModuleNotFoundError: No module named 'lxml'
- suggest braces around empty body in an 'if' statement
- MySQL 拷贝数据库表方式备份,还原后提示 table xxx '' doesn`t exist
- 【Mybatis异常】 org.apache.ibatis.binding.BindingException: Parameter 'storeId' not found. Available parameters are [form, param1]
- jQuery源码分析系列(39) : 动画队列
- Python 中的 if __name__ == '__main__' 该如何理解
- [Javascript] Javascript 'in' opreator
- [PWA] 9. Service worker registerion && service work's props, methods and listeners
- [Javascript] Regex: '$`', '$&', '$''
- HTTP request is unauthorized with client authentication scheme 'Anonymous'.
- 《从零开始学Swift》学习笔记(Day 39)——构造函数重载
- Neither BindingResult nor plain target object for bean name 'command' available as request attribute
- 'svn'不是内部或外部命令,也不是可运行的程序或批处理文件
- error C2338: You've instantiated std::aligned_storage<Len, Align> with an extended alignment (in other words, Align >
- 39. SAP UI5 应用出现白屏的一些常见错误和分析方法分享
- 【Good Bye 2020 F】Euclid's nightmare
- 【CS Round #39 (Div. 2 only) C】Reconstruct Sum
- [LeetCode] 39. Combination Sum ☆☆☆(数组相加等于指定的数)
- POJ 2965:The Pilots Brothers' refrigerator
- RuntimeError: Function 'AddmmBackward' returned nan values in its 2th output.