spring自定义注解

39. 组合总和

难度中等1001收藏分享切换为英文接收动态反馈

给定一个无重复元素的数组 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]
]

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

通过次数172,408

提交次数241,129

题解

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<>();
        if( candidates == null || candidates.length ==0) return res;
        Arrays.sort(candidates); // 排序是减枝的基础
        traceBack(  candidates,  new LinkedList<Integer>(), 0, 0, target, res);
        return res;
    }

    void traceBack(int[] candidates,LinkedList<Integer> temp ,int sum ,int start, int target,List<List<Integer>> res){
        if(sum == target){
            res.add( new LinkedList<>(temp));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            if(sum > target) break; //如果 sum > target 则后面的都不需要继续 循环了 ，直接退出
            temp.add(candidates[i]);
            sum+= candidates[i];
            traceBack( candidates, temp, sum ,  i, target, res);
            temp.pollLast();
            sum-=candidates[i];
        }
    }
}

---

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。

作者：cherry-n1
链接：https://leetcode-cn.com/problems/combination-sum/solution/zu-he-zong-he-hui-su-jian-zhi-wu-jian-zhi-by-cherr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com