Leetcode算法Java全解答--39. 组合总和.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答--39. 组合总和

[toc]

题目

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。 解集不能包含重复的组合。

示例:

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

想法

// TODO

结果

// TODO

总结

// TODO

代码

我的答案

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        Arrays.sort(candidates); // 剪枝
        dfs(candidates, resultList, result, 0, target);
        return resultList;
    }

    private void dfs(int[] candidates, List<List<Integer>> resultList, List<Integer> result, int start, int target) {
        if (target < 0){            // target不符合
            return;
        }else if (target == 0){   // target符合
            resultList.add(new ArrayList<>(result));
        }else {                  // 继续进行数的查找
            for (int i = start; i < candidates.length; i++){
                result.add(candidates[i]);
                dfs(candidates, resultList, result, i, target - candidates[i]);
                result.remove(result.size() - 1);     // 数查找完后要进行回溯
            }
        }
    }
  

大佬们的答案

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        getResult(result, new ArrayList<Integer>(), candidates, target, 0);
        return result;
    }

    private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start) {
        if (target > 0) {
            for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
                cur.add(candidates[i]);
                getResult(result, cur, candidates, target - candidates[i], i);
                cur.remove(cur.size() - 1);
            }//for
        }//if
        else if (target == 0) {
            result.add(new ArrayList<Integer>(cur));
        }//else if
    }
}

测试用例


其他

代码托管码云地址:https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈:https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060