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] ]1、使用backtrack 来解决问题
2、注意
temp_list.remove(temp_list.size() - 1);如果回溯到上一层的话要把最后的一个数从ArrayList 中拿出来
public class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); backtrack(res, new ArrayList<Integer>(), candidates, target, 0); return res; } private void backtrack(List<List<Integer>> res, List<Integer> temp_list, int[] nums, int remain, int pos) { if (remain < 0) return; else if (remain == 0) res.add(new ArrayList<>(temp_list)); else { for (int i = pos; i < nums.length; i++) { temp_list.add(nums[i]); backtrack(res, temp_list, nums, remain - nums[i], i); temp_list.remove(temp_list.size() - 1); } } } }