leetcode 39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1 public class _39 { 2 3 private void result(int[] candidates, int target, int sum,int cur,List<Integer> subset, List<List<Integer>> res){ 4 if (sum > target) 5 return ; 6 if (sum == target){ 7 List<Integer> e = new ArrayList<>(); 8 e.addAll(subset); 9 res.add(e); 10 return ; 11 } 12 for (int i = cur; i < candidates.length; ++i){ 13 subset.add(candidates[i]); 14 if (sum + candidates[i] <= target) 15 result(candidates, target, sum + candidates[i],i, subset, res); 16 subset.remove(subset.size()-1); 17 } 18 19 } 20 21 public List<List<Integer>> combinationSum(int[] candidates, int target) { 22 List<List<Integer>> res = new ArrayList<>(); 23 List<Integer> subset = new ArrayList<>(); 24 // Arrays.sort(candidates); 25 result(candidates,target, 0,0, subset, res); 26 return res; 27 } 28 29 30 public static void main(String[] args) { 31 List<List<Integer>> lists = new _39().combinationSum(new int[]{2,3,6,7}, 7); 32 for (List<Integer> e : lists){ 33 System.out.println(e); 34 } 35 } 36 }