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:
All numbers (including target) will be positive integers.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] ]
代码如下：
import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class CombinationSum { public List<ArrayList<Integer>> combinationSum(int[] nums,int target){ List<ArrayList<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list,new ArrayList<>(),nums,target,0); return list; } private void backtrack(List<ArrayList<Integer>> list, ArrayList<Integer> arrayList, int[] nums, int target, int start) { if(target<0) return; else if(target == 0) list.add(new ArrayList<>(arrayList)); else{ for(int i=start;i<nums.length;i++){ arrayList.add(nums[i]); backtrack(list,arrayList,nums,target-nums[i],i);//不是i+1，因为我们可以重用相同的元素 arrayList.remove(arrayList.size()-1); } } } }