- 浏览: 171722 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 221Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 219You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 336Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 325Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 443Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 498Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 423Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 611Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 420The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 378Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 511Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 521Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 364All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 853Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 876Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 547Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 592Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 757Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 724You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 623For a undirected graph with tre ...
相关推荐
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
Combination Sum III Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest...
Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 ...
combinationSum ( self , candidates , target ): def backtrack ( tmp , start , end , target ): if target == 0 : ans . append ( tmp [:]) elif target > 0 : for i in range ( start , end ): tmp . append ( ...
python实现基本算法 所有组合 所有排列 所有子序列 ... Combination Sum Hamiltonian Cycle Knight Tour Minimax Minmax N Queens N Queens Math Rat In Maze Sudoku Sum Of Subsets Word Search
leetcode打不开Leetcode Note Tips Tip1: Two pointer ...Combination Sum II) Tip5: 鸽笼原理要记得,如果题目说要constant extra space,八成就是用input array + swap(#41. First Missing Positive
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、...Combination Sum组合总和 Combination Sum II组合总和 II Permutations全排列 Permutations II全排列 II Maximum Suba
39/Sum.Combination Sum 40/Sum.Combination Sum 2 46.排列(回串) 47/46.排列 2 48.旋转矩阵 49.组字谜 50.(跳过)(坏问题) 53.最大子阵列 54/59.螺旋矩阵 55.跳跃游戏 57.插入间隔 58.(跳过)(Python把戏) 59....
039:Combination Sum 040:Combination Sum II 046:Permutations 047:Permutations II 051:N-Queens 052:N-Queens II 071: Letter Combinations of a Phone Number 093:Restore IP Addresses 树的遍历问题也...
利用双向链表模拟动态分区分配方式。。。。
CombinationSum 组合之和 完成 LinkedList 题目 说明 状态 AddTwoNumber 两数相加 完成 SwapPairs 两两交换链表中的节点 完成 String 题目 说明 状态 LongestSubstring 最长子串 完成 LongestPalindrome 最长回文...
def combinationSum(self, candidates, target): """ :type candidates: List[int] :type target: int :rtype: List[List[int]] """ result,temp = [],[] self.combinationSumRecu(sorted(candidates),...
Leetcode\combination sum(39).swift Leetcode\count number of team(1395).swift Leetcode\counting bits(338).swift Leetcode \find 数组中的所有重复项(442).swift Leetcode\find peak element(162).swift ...
leetcode 2 Useful Links ...Sum], [17 Phone Num] [] BFS [] [] [] DP , [53 max subarray], , [96 DP | BST], , [] [] Binary Search , , [74 2D matrix] [] Slicing Window / Two Pointers [918 Ma
算法 数据结构,算法,动态程序,递归和一点编码的乐趣! 介绍 ...CombinationSum:数组中组合的总和 CompareArrayBST:比较二进制搜索树 DecodeNumber:解码号码的几种方法 FindMiddleShiftedSorted
leetcode 2 和 c Leetcode_imp_C Leetcode 在 C 上的实现 大批: leetcode_0001_two_sum.c leetcode_0011_max_area.c leetcode_0015_three_sum.c ...leetcode_0039_combination_sum.c 40 leetcode_0041_first_miss
func combinationSum(candidates []int, target int) (res [][]int) {path := []int{}sort.Ints(candidates)var dfs func(int, int)dfs = func(target, index int) {if target <= 0 {if target == 0 {res = ...
a program for find combination of N Number to reach a Sum. this solve sudoku puzzle.
Sum Letter Combination of a Photo Number Palindrome Par 第一节课内容结束,题目训练. 详情 Binary Search Tree (二叉查找树) 第二次课, Binary Search Tree T(n) = O(1) + T( n/2) = O(log n) T(n) = O(1) + ...
combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 - find the only element which...