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

2023-12-22 23:54:00

题目

给你一个?无重复元素?的整数数组?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);
    }
}

文章来源:https://blog.csdn.net/qq_45794129/article/details/135149131
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。