Combination Sum

xiaoxiao2021-02-28  8

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.


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); } } } }