​LeetCode刷题实战39:组合总和

共 2331字,需浏览 5分钟

 ·

2020-09-16 21:18

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


今天和大家聊的问题叫做 组合总和,我们先来看题面:

https://leetcode-cn.com/problems/combination-sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.


The same repeated number may be chosen from candidates unlimited number of times.


Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

题意


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

题解

回溯法

回溯算法关键在于:不合适就退回上一步,然后通过约束条件, 减少时间复杂度.

假设candidates = [2, 3, 6, 7],target = 7
以 target = 7 为根结点,每一个分支做减法。减到 0 或者负数的时候,剪枝。其中,减到 0 的时候结算,这里 “结算” 的意思是添加到结果集。



代码如下:

class Solution {
    public List> combinationSum(int[] candidates, int target) {
        List> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, res, 0, new ArrayList());
        return res;
    }
    private void backtrack(int[] candidates, int target, List> res,
        int i, ArrayList tmp_list
)
{
        if (target < 0) return;
        if (target == 0) {
            res.add(new ArrayList<>(tmp_list)); return;
        }
        for (int start = i; start < candidates.length; start++) {
            if (target < candidates[start]) break;
            tmp_list.add(candidates[start]);
            backtrack(candidates, target - candidates[start], res, start, tmp_list);
            tmp_list.remove(tmp_list.size() - 1);
        }
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。


上期推文:


LeetCode1-20题汇总,速度收藏!
LeetCode刷题实战21:合并两个有序链表
LeetCode刷题实战23:合并K个升序链表
LeetCode刷题实战24:两两交换链表中的节点
LeetCode刷题实战25:K 个一组翻转链表
LeetCode刷题实战26:删除排序数组中的重复项
LeetCode刷题实战27:移除元素
LeetCode刷题实战28:实现 strStr()
LeetCode刷题实战29:两数相除
LeetCode刷题实战30:串联所有单词的子串
LeetCode刷题实战31:下一个排列
LeetCode刷题实战32:最长有效括号
LeetCode刷题实战33:搜索旋转排序数组
LeetCode刷题实战34:在排序数组中查找元素
LeetCode刷题实战35:搜索插入位置
LeetCode刷题实战36:有效的数独
LeetCode刷题实战37:解数独
LeetCode刷题实战38:外观数列


浏览 33
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报