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:
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
public class Solution { public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { // Start typing your Java solution below // DO NOT write main() function Arrays.sort(candidates) ; ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> temp = new ArrayList<Integer>(); combination(candidates, target, 0, 0, temp, result); return result; } private void combination(int[] candidates, int target, int sum, int start, ArrayList<Integer> combin, ArrayList<ArrayList<Integer>> result) { //check add if(sum > target) return; if(sum == target) { result.add(combin); return; } for(int i = start; i < candidates.length; i++) { ArrayList<Integer> temp = new ArrayList<Integer>(combin);//add new item to list temp.add(candidates[i]); combination(candidates, target, sum + candidates[i], i, temp, result);//next time start at same location ie. first time 2 second t//ime 2... } } }
mistake: each time sum has to be do inside recursion(sum + candidates[i]), other wise will add twice
这个题是一个NP问题，方法仍然是N-Queens中介绍的套路。基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的. 注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。这道题有一个非常类似的题目Combination Sum II，有兴趣的朋友可以看看，一次搞定两个题哈。
public class Solution { public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { // Start typing your Java solution below // DO NOT write main() function Arrays.sort(candidates) ; ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list =new ArrayList<Integer>(); recursion(result,list,candidates,target,0); return result; } public void recursion(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list,int[] candidates,int target,int start ){ if(target< 0) return; if(target == 0) { result.add(list); return; } for(int i = start ; i < candidates.length ; i++){ ArrayList<Integer> temp = new ArrayList<Integer>(list); temp.add(candidates[i]); recursion(result,temp,candidates,target-candidates[i],i); } } }
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates) ; List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> list = new ArrayList<Integer>(); dfs(result,list,candidates,target,0); return result; } public void dfs(List<List<Integer>> result,List<Integer> list,int[]candidates,int target,int start ){ if( target < 0) return; else if(0 == target){ result.add(new ArrayList<Integer>(list)); return; } for(int i = start ; i < candidates.length; i++){ list.add(candidates[i]); dfs(result,list,candidates,target-candidates[i],i); list.remove(list.size()-1); } } }