Combination Sum

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] ]

Solution1:

public List<List<Integer>> combinationSum(int[] candidates, int target) { return combinationSum(candidates, candidates.length - 1, target); } public List<List<Integer>> combinationSum(int[] candidates, int len, int target) { List<List<Integer>> result = new ArrayList<>(); for (int i = len; i >= 0; i--) { if (candidates[i] < target) { List<List<Integer>> lists = combinationSum(candidates, i, target - candidates[i]); if (!lists.isEmpty()) { for (List<Integer> list : lists) { list.add(candidates[i]); } result.addAll(lists); } } if (candidates[i] == target) { List<Integer> list = new ArrayList<>(); list.add(candidates[i]); result.add(list); } } return result; }

Solution2:

public List<List<Integer>> combinationSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } PRivate void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) { if (remain < 0) return; else if (remain == 0) list.add(new ArrayList<>(tempList)); else { for (int i = start; i < nums.length; i++) { tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i); tempList.remove(tempList.size() - 1); } } }