题目
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。
解题思路
- 对数组进行排序；
- 递推寻找合适的元素；
- 当目标结果为0时添加到返回结果中；
- 当索引越界或目标值小于0时返回停止当前递推；
- 因为允许重复获取同一元素，所以分两种，一种下一元素还是当前元素，另一种为索引后推。
代码展示
class Solution { List<List<Integer>> ans = new ArrayList<>(); int[] candidates; int len; public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); this.candidates = candidates; len = candidates.length; dfs(0,target, new ArrayList<>()); return ans; } private void dfs(int index, int target, List<Integer> list){ if(target == 0){ ans.add(new ArrayList<>(list)); return; } if(index >= len || target < 0){ return; } if(candidates[index] <= target){ list.add(candidates[index]); dfs(index, target - candidates[index], list); list.remove(list.size() - 1); } dfs(index + 1, target, list); } }
