还是递归 但是边界条件以及边界上的处理不容易搞清楚(一开始我就把target==0的情况漏掉了,然后又把target==0放在了target<0||candidates.length<=0的后面,导致candidates.length==0&&target==0的情况不会被target==0处理,唉,考虑不清楚)
汗 II就直接改了改代码通过了。。。
public class Solution { public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (target == 0){ results.add(new ArrayList<Integer>()); return results; } if (target < 0 || candidates.length <= 0) return results; int[] newCandidates = Arrays.copyOfRange(candidates, 0, candidates.length-1); int max = candidates[candidates.length-1]; int num = target / max; for (int i = 0; i <= num; ++i){ ArrayList<ArrayList<Integer>> newResults = combinationSum(newCandidates, target-i*max); for (int j = 0; j < newResults.size(); ++j) for (int k = 0; k < i; ++k) newResults.get(j).add(max); results.addAll(newResults); } return results; } }
汗 II就直接改了改代码通过了。。。
public class Solution { public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>(); if (target == 0){ results.add(new ArrayList<Integer>()); return results; } if (target < 0 || candidates.length <= 0) return results; int[] newCandidates = Arrays.copyOfRange(candidates, 0, candidates.length-1); int max = candidates[candidates.length-1]; for (int i = 0; i <= 1; ++i){ ArrayList<ArrayList<Integer>> newResults = combinationSum2(newCandidates, target-i*max); for (int j = 0; j < newResults.size(); ++j) for (int k = 0; k < i; ++k) newResults.get(j).add(max); for (int j = 0; j < newResults.size(); ++j) if (!results.contains(newResults.get(j))) results.add(newResults.get(j)); } return results; } }
发表评论
-
Insert Interval
2012-11-11 01:33 541各种条件真复杂,不仅是边界条件,而且还要分很多种情况讨论 而且 ... -
Implement strStr()
2012-11-07 15:44 581唉 终于到了要记算法的时候了 KMP。。。还没写完 回去再写。 ... -
Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code
2012-11-07 00:08 1091Flatten太简单了 递归 一遍过 oh yeah = = ... -
First Missing Positive
2012-11-06 22:50 588唉 想了很久都没想出来 后来还是看了网上的答案 >_&l ... -
Edit Distance
2012-11-06 00:27 668动规 就是递推。。。比较难想 然后数组长度设置比字符串长度多一 ... -
Divide Two Integers
2012-11-05 00:12 711自己实现除法 太太太恶心了。。。。 就是用位移代替了乘法,然后 ... -
Distinct Subsequences
2012-11-04 21:44 657动规,从前到后用T的每一个字符i,扫描S的每一个字符j。维护一 ... -
Count and Say
2012-11-04 18:46 690public class Solution { ... -
Convert Sorted Array to Binary Search Tree && Convert Sorted List to Binary Sear
2012-11-04 17:36 826/** * Definition for binary ... -
Container With Most Water
2012-11-04 00:25 697本来以为是个简单的题目,直接二重循环,结果小测试过了,大测试超 ... -
Construct Binary Tree from Inorder and Postorder Traversal
2012-11-03 23:40 745不知道为什么错了。。。eclipse上明明是正确的啊 leet ... -
Combinations
2012-11-03 22:19 603全排列 按理说很简单,可是用递归写,边界条件就还是难想清楚,s ... -
climbing stairs
2012-11-03 17:18 608一开始觉得是简单的组合数学题,但是写完之后发现,首先组合数不是 ... -
Binary Tree Inorder Traversal
2012-11-02 23:51 613I简单 直接递归就好 addAll函数很好用 /** ... -
Best Time to Buy and Sell Stock I & II
2012-11-02 22:05 1042啊 第一次直接过small和big测试 好爽!虽然主要是以前知 ... -
Balanced Binary Tree
2012-11-01 23:38 609/** * Definition for binary ... -
Anagrams
2012-10-31 00:33 586这题实在是没懂它的意思。。。囧啊 import java. ... -
Add Two Numbers
2012-10-30 23:03 613这题不难 直接上递归就行 /** * Definiti ... -
Add Binary
2012-10-29 00:07 596public String addBinary(Strin ... -
4Sum
2012-10-27 22:49 734本来以为只要在3Sum外面再包一层循环就好了,可是。。。在Ju ...
相关推荐
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
Combination of HPLC chromatogram and hypoglycemic effect identifies isoflavones as the principal active fraction of Belamcanda chinensis leaf extract in diabetes treatment.
This specification is intended to be used in combination with the appropriate certification process, and subject to conformance by the manufacturers to the CI Plus Compliance and Robustness Rules....
排列组合01法的Java实现,实现基于字典排序的结果输出
JavaFX+Jfoenix 学习笔记系列文章JavaFX+Jfoenix 学习笔记(九)--KeyCombination快捷键源码
CST STUDIO SUITE micaro usage in VBA programming. a good start for combination of CST & VBA.
The intelligent surfer probabilistic combination of link and content information in pagerank
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 ( ...
Sum[i:j] = Sum[0:j] - Sum[0:i] for continuous array (# Array 560. Subarray Sum Equals K) Tip3: Knapsack Problem (0/1, unbounded) (#DP 322. Coin Change) Tip4: backtrace or K sum remove duplicates if i ...
Combination Sum Medium 回溯 0040 Combination Sum II Medium 回溯 0046 Permutations Medium 回溯 0047 Permutations II Medium 递归、回溯 0051 N-Queens Hard 回溯 0053 Maximum Subarray Easy 动态规划 0069 ...
Combination Sum II 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 ...
HDLbits答案Combination_logic
p2pgrid-combination.pdf
engine-combination.c
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 = ...
组合公式,可以用来求解数学中的组合,谢谢大家的使用
结合先验知识,学习贝叶斯网络的文档,可以看看
What a combination-using free, open-source Blender software and the SI02 game engine to create very cool 3D characters and games for the very hot devices of the moment, the iPhone and iPod Touch....
java Combination ABCD i 输出 { {}, {D}, {C}, {D, C}, {B}, {D, B}, {C, B}, {D, C, B}, {A}, {D, A}, {C, A}, {D, C, A}, {B, A}, {D, B, A}, {C, B, A}, {D, C, B, A} } 输入 java Combination abcd r 输出 { {a...