39. 组合总和 --力扣 --JAVA

题目

给你一个?无重复元素?的整数数组?candidates?和一个目标整数?target?，找出?candidates?中可以使数字和为目标数?target?的 所有?不同组合?，并以列表形式返回。你可以按?任意顺序?返回这些组合。

candidates?中的?同一个?数字可以?无限制重复被选取?。如果至少一个数字的被选数量不同，则两种组合是不同的。?

对于给定的输入，保证和为?target?的不同组合数少于?150?个。

解题思路

1. 对数组进行排序；
2. 递推寻找合适的元素；
3. 当目标结果为0时添加到返回结果中；
4. 当索引越界或目标值小于0时返回停止当前递推；
5. 因为允许重复获取同一元素，所以分两种，一种下一元素还是当前元素，另一种为索引后推。

代码展示

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