Leetcode: Combination Sum III
LeetCode sum III combination
2023-09-11 14:14:07 时间
ind 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]]
Use recursion, or DFS
One syntax to notice is line 3:
List<List<Integer>> res = new ArrayList<List<Integer>>();
List is abstract and can not be instantiated
1 public class Solution { 2 public List<List<Integer>> combinationSum3(int k, int n) { 3 List<List<Integer>> res = new ArrayList<List<Integer>>(); 4 List<Integer> item = new ArrayList<Integer>(); 5 helper(res, item, k, n, 1); 6 return res; 7 } 8 9 public void helper(List<List<Integer>> res, List<Integer> item, int num, int remain, int start) { 10 if (remain < 0) return; 11 if (num == 0) { 12 if (remain == 0) { 13 res.add(new ArrayList<Integer>(item)); 14 } 15 return; 16 } 17 for (int i=start; i<=9; i++) { 18 item.add(i); 19 helper(res, item, num-1, remain-i, i+1); 20 item.remove(item.size()-1); 21 } 22 } 23 }
相关文章
- Leetcode: Nested List Weight Sum II
- Leetcode: Binary Tree Maximum Path Sum
- Leetcode: Single Number
- Leetcode: Rotate Image
- [LeetCode][Java] Unique Paths II
- [LeetCode] Reorder List
- [LeetCode] Path Sum
- 【LeetCode】216. Combination Sum III
- 【LeetCode-面试算法经典-Java实现】【015-3 Sum(三个数的和)】
- [leetcode]Two Sum
- Combination Sum III -- leetcode
- LeetCode——Combination Sum II
- 【leetcode】107 : 二叉树的层序遍历 II
- [LeetCode] 1191. K-Concatenation Maximum Sum K次串联后最大子数组之和
- [LeetCode] 1186. Maximum Subarray Sum with One Deletion 删除一次得到子数组最大和
- [LeetCode] 1038. Binary Search Tree to Greater Sum Tree 二叉搜索树到较大和树
- [LeetCode] 1005. Maximize Sum Of Array After K Negations K次取反后最大化的数组和
- [LeetCode] 789. Escape The Ghosts 逃离鬼魂
- [LeetCode] 706. Design HashMap 设计HashMap
- [LeetCode] Minimum Index Sum of Two Lists 两个表单的最小坐标和
- [LeetCode] Split Array with Equal Sum 分割数组成和相同的子数组
- [LeetCode] 364. Nested List Weight Sum II 嵌套链表权重和之二
- [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计
- [LeetCode] 307. Range Sum Query - Mutable 区域和检索 - 可变
- [LeetCode] 113. Path Sum II 二叉树路径之和之二
- LeetCode将有序数组转换为二叉搜索树
- Leetcode——21. Merge Two Sorted Lists
- leetcode 437. Path Sum III 路径总和 III(中等)
- leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球(中等)