Combination Sum
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.
For example, given candidate set 2,3,6,7 and target 7, A solution set
is: [7] [2, 2, 3]
思路： 把target number 传入， 每次加入一个数字，就把target number 减去这个数字递归。 当target number == 0 时，说明此时list中的数字的和为target number。 就可以将这组数字加入list里面。 注意可以重复加数字， 所以每次递归传的index就是i。
public class Solution { public List> combinationSum(int[] candidates, int target) { List> result = new ArrayList>(); List list = new ArrayList(); Arrays.sort(candidates); int sum = target; helper(result,list, sum,candidates,0); return result; } private void helper(List> result, List list,int sum, int[] candidates,int index) { if (sum == 0) { result.add(new ArrayList(list)); return; } for (int i = index; i < candidates.length; i++) { if (sum < 0) { break; } list.add(candidates[i]); helper(result,list, sum - candidates[i], candidates,i); list.remove(list.size() - 1); } }}关键字：list, sum, target