Combination Sum III -- leetcode
LeetCode -- sum III combination
2023-09-11 14:20:45 时间
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Credits:
基本思路:
使用dfs进行穷举遍历。
因为结果集要求按升序排列,则先选择较小的数字,然后从剩下的较大数中进行选择。
确保每次选择的数都大于上次选择的。
class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans; vector<int> seq; helper(ans, seq, k, n); return ans; } void helper(vector<vector<int>>& ans, vector<int>& seq, int k, int n) { if (!k && !n) return ans.push_back(seq); if (!k || n<0) return; int start = seq.empty() ? 1 : seq.back()+1; for (int i=start; i<=9; i++) { seq.push_back(i); helper(ans, seq, k-1, n-i); seq.pop_back(); } } };
相关文章
- Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 384 打乱数组
- Java实现 LeetCode 132 分割回文串 II(二)
- Java实现 LeetCode 33 搜索旋转排序数组
- LeetCode(106):从中序与后序遍历序列构造二叉树
- Python 刷Leetcode题库,顺带学英语单词(26)
- Leetcode 1598. 文件夹操作日志搜集器
- [LeetCode] 46. Int数组全排列 ☆☆☆(回溯)
- [LeetCode] 112. Path Sum ☆(二叉树是否有一条路径的sum等于给定的数)
- Reorder List -- leetcode
- 【Leetcode】Search a 2D Matrix
- leetcode -- Maximum Subarray
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】234.回文链表