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

题目

解题思路

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