- 浏览: 182800 次
- 性别:
- 来自: 济南
文章分类
最新评论
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]]
找出所有可能的组合,使组合中元素的个数等于k, 元素的和等于n。我们采用回溯法,当元素的个数为k并且和为9的时候我们记录这个结果,然后回溯,继续寻找其他可能的结果。代码如下:
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]]
找出所有可能的组合,使组合中元素的个数等于k, 元素的和等于n。我们采用回溯法,当元素的个数为k并且和为9的时候我们记录这个结果,然后回溯,继续寻找其他可能的结果。代码如下:
public class Solution { public List<List<Integer>> combinationSum3(int k, int n) { LinkedList<Integer> list = new LinkedList<Integer>(); List<List<Integer>> result = new ArrayList<List<Integer>>(); getCombinations(1, k, n, list, result); return result; } public void getCombinations(int start, int k, int n, LinkedList<Integer> list, List<List<Integer>> llist) { if(list.size() == k && n == 0) { llist.add(new LinkedList<Integer>(list)); } for(int i = start; i <= 9; i++) { if(list.size() < k) { list.add(i); getCombinations(i + 1, k, n - i, list, llist); list.removeLast(); } } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 264Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 266You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 381Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 373Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 560Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 474Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 661Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 468The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 427Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 571Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 576Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 423All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 894Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 928Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 669Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 841Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 780You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 703For a undirected graph with tre ...
相关推荐
java java_leetcode题解之Combination Sum III.java
leetcode Java 246 題目及...240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses 589 244 Reverse Integer 591 245 Palindrome Number 593
代码首先定义了一个名为`Solution`的类,其中有两个方法:`bit1Count`和`combinationSum3`。`bit1Count`方法用于计算一个无符号整数中二进制形式的1的个数,而`combinationSum3`是解决该问题的主要方法。 在`bit1...
java java_leetcode题解之Combination Sum.java
java java_leetcode题解之Combination Sum IV.java
java java_leetcode题解之Combination Sum II.java
python python_leetcode题解之216_Combination_Sum_III.py
java入门 java_leetcode题解之039_Combination_Sum
js js_leetcode题解之39-combination-sum.js
c语言入门 C语言_leetcode题解之39-combination-sum.c
js js_leetcode题解之40-combination-sum-II.js
c语言入门 C语言_leetcode题解之40-combination-sum-ii.c
def combinationSum3(self, k: int, n: int, m: int, current_sum=0, current_combination=[], combinations=[]): if len(current_combination) == m and current_sum == k: combinations.append(current_...
Combination Sum组合总和 Crossword Puzzle Solver 填字游戏求解器 Generate Parentheses 生成括号 Hamiltonian Cycle 哈密顿循环 Knight Tour骑士之旅 Match Word Pattern 匹配单词模式 Minimax极大 极小 N QueensN...
public static List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList(); List<Integer> combination = new ArrayList(); Arrays.sort(candidates);...
在主函数`combinationSum2`中,我们先对输入的`candidates`进行排序,然后调用`backtrack`函数开始搜索过程。最终返回的结果集`res`包含了所有满足条件的组合。 通过以上代码,我们可以解决LeetCode第40题...
Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 ...
\[ f(t) = \sum_{n=1}^{\infty} A_n \sin(n\omega_0 t + \phi_n) \] 其中,\(A_n\) 表示第 \(n\) 个正弦波的振幅,\(n\omega_0\) 是其频率(\(n\) 为整数,\(\omega_0\) 是基频),\(\phi_n\) 是相位偏移。对于余弦...
最后,`combinationSum2`是对外的公共接口,它初始化结果向量`vvi`,并调用`helper`函数开始搜索过程。 总的来说,这个手稿展示了如何使用C++实现一个基于回溯和剪枝的解决方案,来解决组合问题。通过理解这个示例...