首页 > 代码库 > leetcode 216. Combination Sum III 求和III ---------- java
leetcode 216. Combination Sum III 求和III ---------- java
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.
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]]
由于限定了1-9所以比较简单,枚举就可以。让答案数组升序排列,然后向里面放入数就可以了。
tips:用数组要比用ArrayList快。
public class Solution { public List<List<Integer>> list; public List<List<Integer>> combinationSum3(int k, int n) { list = new ArrayList(); if (n > (18 - k + 1) * k / 2 || n < (1 + k) * k / 2 || k > 9){ return list; } int[] nums = new int[k]; for (int i = 1; i <= 10 - k; i++){ nums[0] = i; getSum(nums, n, 0, k - 1); } return list; } public void getSum(int[] ans, int n, int pos, int k){ if (k == 0){ int sum = 0; for (int i = 0; i < ans.length; i++){ sum += ans[i]; } if (sum == n){ List<Integer> ll = new ArrayList(); for (int i : ans){ ll.add(i); } list.add(ll); } return ; } for (int i = ans[pos] + 1; i <= 10 - k; i++){ ans[pos + 1] = i; getSum(ans, n, pos + 1, k - 1); } } }
leetcode 216. Combination Sum III 求和III ---------- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。