Given a set of candidate numbers (C) (without duplicates) 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 { List<List<Integer>> result; List<Integer> current; public List<List<Integer>> combinationSum(int[] candidates, int target) { result = new ArrayList<>(); if (candidates == null || candidates.length == 0) { return result; } current = new ArrayList<>(); helper(candidates, target); return result; } public void helper(int[] candidates, int target) { if (target == 0) { //Remove duplicates List<Integer> tmp = new ArrayList<>(current); Collections.sort(tmp); if (!result.contains(tmp)) { result.add(tmp); } return; } if (target < 0) { return; } for (int i = 0; i < candidates.length; i++) { current.add(candidates[i]); helper(candidates, target - candidates[i]); current.remove(current.size() - 1); } } }
But it can be optimized a lot by sort the input first and don‘t look back.
public class Solution { List<List<Integer>> result; List<Integer> current; public List<List<Integer>> combinationSum(int[] candidates, int target) { result = new ArrayList<>(); if (candidates == null || candidates.length == 0) { return result; } Arrays.sort(candidates); current = new ArrayList<>(); helper(candidates, target, 0); return result; } public void helper(int[] candidates, int target, int start) { if (target == 0) { result.add(new ArrayList<>(current)); return; } if (target < 0) { return; } for (int i = start; i < candidates.length && target >= candidates[i]; i++) { current.add(candidates[i]); helper(candidates, target - candidates[i], i); current.remove(current.size() - 1); } } }
但是第二种方法在lintcode上是过不了的。如果input是[2, 2, 3]就会出现重复。如果面试遇到可以问问input会不会有重复。可以加一步判断，但没有必要排序了，因为加进去的本身就已经排序了。
我发现dfs的套路还都挺像的，注意一下有start的地方就好了。同时arraylist也可以作为参数传递。
原文：http://www.cnblogs.com/aprilyang/p/6565020.html