Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
2,3,6,7
and target 7
, A solution set is:
[7]
[2, 2, 3]
A:public class CombinationSum { public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { // first sort the array Arrays.sort(candidates); return combinationSum(candidates,0, target); } private ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int startIndex, int target) { // use startIndex as the first starting index of candidates, to // calculate the sum ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); if (target < 0 || startIndex>= candidates.length) { return all; } if(target == candidates[startIndex]){ ArrayList<Integer> al = new ArrayList<Integer>(); al.add(target); all.add(al); } // if we do NOT use the startIndex value all.addAll( combinationSum(candidates,startIndex+1, target)); // if we use one startIndex value ArrayList<ArrayList<Integer>> nextAll = combinationSum(candidates,startIndex, target- candidates[startIndex]); combineResult(all,nextAll,candidates[startIndex]); return all; } private void combineResult(ArrayList<ArrayList<Integer>> all, ArrayList<ArrayList<Integer>> nextAll, int firstValue) { // combine the nextAll into all for(int i =0;i<nextAll.size();i++){ ArrayList<Integer> al = nextAll.get(i ); al.add(0 , firstValue); all.add(al); } } }
Mistakes:
1: 利用递归调用,基础条件检验的时候,忘了检测 startIndex是否越界。
2:肏, 忘了最基本的, 当条件符合的时候,就加上,并且返回啊。 检查target 是否和第一个数字吻合。
Learned:
----------------------------------第二遍-----递归的时候, 把所有的index after beginIndex 都用for loop遍历了一遍,造成了,极大的重复-----------------
----------------------第三遍也是 同样的错误, 哎~~~~~~~~~~~~~~~
public class Solution { public ArrayList<ArrayList<Integer>> combinationSum(int[] A, int target) { Arrays.sort(A); return helper(A, 0, target); } private ArrayList<ArrayList<Integer>> helper(int[] A, int start, int target) { ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>(); if (start >= A.length || target < A[start]) return all; if (target == A[start]) { ArrayList<Integer> al = new ArrayList<Integer>(); al.add(target); all.add(al); return all; } // target > A[start], we can continue to divide it // use A[i] ArrayList<ArrayList<Integer>> less1 = helper(A, start, target - A[start]); for (int j = 0; j < less1.size(); j++) less1.get(j).add(0, A[start]); all.addAll(less1); // do not use A[i]; less1 = helper(A, start + 1, target); all.addAll(less1); return all; } }
No comments:
Post a Comment