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.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
回溯算法(backtracking)，因为每个数可以使用任意次，所以每次递归的时候都从当前的起点开始
public class Solution { /** * @param candidates: A list of integers * @param target:An integer * @return: A list of lists of integers */ public List<List<Integer>> combinationSum(int[] candidates, int target) { // write your code here List<List<Integer>> result = new ArrayList<List<Integer>>(); if(candidates == null || candidates.length == 0) return result; List<Integer> line = new ArrayList<Integer>(); Arrays.sort(candidates); helper(result, line, candidates, target, 0); return result; } public void helper(List<List<Integer>> result, List<Integer> line, int[] candidates, int target, int start){ if(target < 0) return; if(target == 0){ result.add(new ArrayList<Integer>(line)); return; } for(int i = start; i < candidates.length; i++){ line.add(candidates[i]); helper(result, line, candidates, target - candidates[i], i); line.remove(line.size() - 1); } return; } }
lintcode-medium-Combination Sum
原文：http://www.cnblogs.com/goblinengineer/p/5281988.html