问题：
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,
[ [7], [2, 2, 3]]
解决：
① 结果要求返回所有符合要求解的题十有八九都是要利用到递归，而且解题的思路都大同小异，需要另写一个递归函数。注意是可以连续选择同一个数加入组合的。与方法②一样
class Solution { //17 ms
public static List<List<Integer>> combinationSum(int[] candidates, int target){ Arrays.sort(candidates); List<List<Integer>> res = new ArrayList<>(); List<Integer> cur = new ArrayList<>(); dfs(candidates,0,target,cur,res); return res; } private static void dfs(int[] candidates, int i, int target, List<Integer> cur, List<List<Integer>> res) {//i表示当前遍历到的下标。 if(target < 0) return; if(target == 0){ res.add(new ArrayList<>(cur)); return; } for(int j = i; j < candidates.length && target >= candidates[j]; j ++){ cur.add(candidates[j]); dfs(candidates,j,target - candidates[j],cur,res);//递归向后查找 cur.remove(cur.size() - 1);//还原链表 } } }② 简化
class Solution { //19ms
List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { List<Integer> cur = new ArrayList<>(); dfs(candidates, 0, target, cur); return res; } private void dfs(int[] nums, int i,int target, List<Integer> cur) {//i表示当前遍历到的位置 if (target == 0) { res.add(new ArrayList<>(cur)); // return; } for (int j = i; j < nums.length; j ++) { if (nums[j] <= target) { cur.add(nums[j]); dfs(nums, j, target - nums[j], cur); cur.remove(cur.size() - 1); } } } }