- 浏览: 173135 次
- 性别:
- 来自: 济南
文章分类
最新评论
关于组合的题目我们一般用回溯法来解决。我的理解回溯法就是按照要求一直找下去,如果找到一个结果就把这个结果记录下来,然后返回上一层,如果有其它路线可以走就继续尝试,如果没有,就继续返回上一层。回溯的实现一般用递归来完成。这里介绍一下关于组合的问题,以及它的一些延伸。
1,Combination
给定两个正整数n和k,返回所有长度为k的组合,组合中的元素为1...n。
例如:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
很明显我们要用链表来记录结果,通过链表的大小来判断是否继续找下去,如果链表长度已经为k,那么就记录这个结果,返回,然后把链表的长度减去1,这样可以继续找其他的结果。当链表的size小于k的时候,我们就继续找下去,知道长度为k。
代码如下:
2,Combination Sum
给定一个数组number[] 和一个目标元素target,在数组中找出所有可能的组合,每个组合中元素的和为target,每个元素可以重复使用。
例如:number[] = {2, 3, 6, 7} target = 7
输出:[7], [2, 2, 3]
我们仍然使用回溯法,这次回溯的条件变为元素的和为target,即当我们遍历的元素的和为target时,我们就找到了一个结果,就把这个结果记录下来,然后返回上一层,继续查找其他结果,不要忘记返回后把链表的长度减1,要不然就不叫回溯了。代码如下:
3,Combination Sum2
给定一个数组numbers[] 和一个目标元素target,从数组中找出所有可能的组合,使组合中元素的和为target,每个元素只能使用一次。
例如:number[] = {10,1,2,7,6,1,5}; target = 8;
输出:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
这道题是combination sum的变形,关键一点时每个元素只能使用一次,只要我们在往下找的时候,不重复当前的元素就可以保证每个元素只能使用一次。代码如下:
4,Combination sum3
给定一个数组numbers[] ={1,2,3,4,5,6,7,8,9}, 一个目标元素target,一个正整数k。输出所有可能的组合,使组合的长度为k,并且组合中元素的和为target,数组中每个元素只能使用一次。
例如:k = 3, target = 9;
输出:[[1,2,6], [1,3,5], [2,3,4]]
这道题与sum2的区别仅在于多了一个限定的长度,因此我们在寻找结果的时候加上一个判断当前组合长度的条件就可以了。代码如下:
1,Combination
给定两个正整数n和k,返回所有长度为k的组合,组合中的元素为1...n。
例如:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
很明显我们要用链表来记录结果,通过链表的大小来判断是否继续找下去,如果链表长度已经为k,那么就记录这个结果,返回,然后把链表的长度减去1,这样可以继续找其他的结果。当链表的size小于k的时候,我们就继续找下去,知道长度为k。
代码如下:
public class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); if(k > n) return llist; combination(1, n, k, list, llist); return llist; } private void combination(int start, int n, int k, LinkedList<Integer> list, List<List<Integer>> llist) { if(list.size() == k) { llist.add(new LinkedList<Integer>(list)); return; } for(int i = start; i <= n; i++) { if(list.size() < k) { list.add(i); combination(i + 1, n, k, list, llist); list.removeLast(); } } } }
2,Combination Sum
给定一个数组number[] 和一个目标元素target,在数组中找出所有可能的组合,每个组合中元素的和为target,每个元素可以重复使用。
例如:number[] = {2, 3, 6, 7} target = 7
输出:[7], [2, 2, 3]
我们仍然使用回溯法,这次回溯的条件变为元素的和为target,即当我们遍历的元素的和为target时,我们就找到了一个结果,就把这个结果记录下来,然后返回上一层,继续查找其他结果,不要忘记返回后把链表的长度减1,要不然就不叫回溯了。代码如下:
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); if(candidates == null) return llist; Arrays.sort(candidates); int end = candidates.length; combinateSum(0, end, candidates, target, list, llist); return llist; } public void combinateSum(int start, int end, int[] candidates, int target, LinkedList<Integer> list, List<List<Integer>> llist) { for(int i = start; i < end; i ++) { if(target - candidates[i] > 0) { list.add(candidates[i]); combinateSum(i, end, candidates, target - candidates[i], list, llist); list.removeLast(); } else if(target == candidates[i]){ list.add(candidates[i]); if(!llist.contains(list)) llist.add(new LinkedList<Integer>(list)); list.removeLast(); } else { return; } } } }
3,Combination Sum2
给定一个数组numbers[] 和一个目标元素target,从数组中找出所有可能的组合,使组合中元素的和为target,每个元素只能使用一次。
例如:number[] = {10,1,2,7,6,1,5}; target = 8;
输出:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
这道题是combination sum的变形,关键一点时每个元素只能使用一次,只要我们在往下找的时候,不重复当前的元素就可以保证每个元素只能使用一次。代码如下:
public class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); if(candidates == null) return llist; Arrays.sort(candidates); combinateSum2(0, target, candidates, list, llist); return llist; } private void combinateSum2(int start, int target, int[] candidates, LinkedList<Integer> list, List<List<Integer>> llist) { for(int i = start; i < candidates.length; i++) { if(target - candidates[i] > 0) { list.add(candidates[i]); combinateSum2(i + 1, target - candidates[i], candidates, list, llist); list.removeLast(); }else if(target == candidates[i]) { list.add(candidates[i]); if(!llist.contains(list)) llist.add(new LinkedList<Integer>(list)); list.removeLast(); } else { return; } } } }
4,Combination sum3
给定一个数组numbers[] ={1,2,3,4,5,6,7,8,9}, 一个目标元素target,一个正整数k。输出所有可能的组合,使组合的长度为k,并且组合中元素的和为target,数组中每个元素只能使用一次。
例如:k = 3, target = 9;
输出:[[1,2,6], [1,3,5], [2,3,4]]
这道题与sum2的区别仅在于多了一个限定的长度,因此我们在寻找结果的时候加上一个判断当前组合长度的条件就可以了。代码如下:
public class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> llist = new ArrayList<List<Integer>>(); LinkedList<Integer> list = new LinkedList<Integer>(); combinateSum3(1, k, n, list, llist); return llist; } private void combinateSum3(int start, int k, int n, LinkedList<Integer> list, List<List<Integer>> llist) { for(int i = start; i <= 9; i++) { if(n - i > 0 && list.size() < k) { list.add(i); combinateSum3(i + 1, k, n - i, list, llist); list.removeLast(); } else if(n == i && list.size() == k - 1) { list.add(i); llist.add(new LinkedList<Integer>(list)); list.removeLast(); } else { return; } } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 425The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ...
相关推荐
239 Combination Sum II 579 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
排列组合01法的Java实现,实现基于字典排序的结果输出
JavaFX+Jfoenix 学习笔记系列文章JavaFX+Jfoenix 学习笔记(九)--KeyCombination快捷键源码
The intelligent surfer probabilistic combination of link and content information in pagerank
Combination of HPLC chromatogram and hypoglycemic effect identifies isoflavones as the principal active fraction of Belamcanda chinensis leaf extract in diabetes treatment.
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 ( ...
p2pgrid-combination.pdf
HDLbits答案Combination_logic
engine-combination.c
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...
组合公式,可以用来求解数学中的组合,谢谢大家的使用
结合先验知识,学习贝叶斯网络的文档,可以看看
An Improvement Using Combination of VQ and PCA Based Techniques
java.combination
Designing a low cost CY7C63723 combination mouse
python实现基本算法 所有组合 所有排列 所有子序列 ... Combination Sum Hamiltonian Cycle Knight Tour Minimax Minmax N Queens N Queens Math Rat In Maze Sudoku Sum Of Subsets Word Search
leetcode题库 Little Algorithm 从 2020 年初开始,我在公众号《面向大象编程》上发表面试算法、...Combination Sum组合总和 Combination Sum II组合总和 II Permutations全排列 Permutations II全排列 II Maximum Suba
CombinationSum 组合之和 完成 LinkedList 题目 说明 状态 AddTwoNumber 两数相加 完成 SwapPairs 两两交换链表中的节点 完成 String 题目 说明 状态 LongestSubstring 最长子串 完成 LongestPalindrome 最长回文...