面试高频算法题之组合问题

简介: 一问搞懂面试中常考的算法组合问题

组合总和

39. 组合总和

问题描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有不同的组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例:

输入:candidates = [2,3,6,7],target = 7

输出:[[2,2,3],[7]]

解释:2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选, 7 = 7 。仅有这两种组合。

分析问题

这道题我们可以采用回溯算法来求解,即列出所有可能的组合,然后在这些组合中筛选出满足条件的序列。

还记得回溯算法的模板吗?如下所示。

result=[]
def backtrack(路径, 选择列表):
    if 满⾜结束条件:
        result.append(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择 

其中

  • 路径:指从 candidates 选择出的元素。
  • 选择列表:指给定的候选集合 candidates 。
  • 结束条件:指路径列表中元素和是否等于目标值target,为了方便处理,我们可以定义一个变量 sum 表示路径中的元素和。

这里需要注意一点,对于求解组合相关的问题,我们需要一个变量start来表示 for 循序的起始位置,即从选择列表的哪个位置开始遍历。

image-20211222143028056

代码如下所示。

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        def backtrack(start, sum, path,candidates):
            #如果路径和大于target,直接返回
            if sum>target:
                return
            #如果路径和等于target,将该路径加入到结果列表中
            if sum==target:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):

                #添加元素到path(做选择)
                path.append(candidates[i])
                #递归查找
                backtrack(i, sum + candidates[i], path, candidates)
                #移除添加的元素(撤销选择)
                path.pop()

        backtrack(0,0,[],candidates)

        return result

通过剪枝进行优化处理

通过分析上述给出的代码,如果 sum 加上一个数已经大于目标值 target,那么 sum 加一个更大的数肯定也是大于target的。基于这个想法,我们可以对上述代码进行优化处理,具体代码如下所示。

image-20211222143803484

class Solution:
    def combinationSum(self, candidates, target):
        result = []
        def backtrack(start, sum, path,candidates):
            #如果路径和等于target,将该路径加入到结果列表中
            if sum==target:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                #剪枝处理
                if sum + candidates[i] > target:
                    break

                #添加元素到path
                path.append(candidates[i])
                backtrack(i, sum + candidates[i], path, candidates)
                #移除添加的元素
                path.pop()
        #排序处理
        candidates.sort()
        backtrack(0,0,[],candidates)
        return result
相关文章
|
2月前
|
负载均衡 NoSQL 算法
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
这篇文章是关于Java面试中Redis相关问题的笔记,包括Redis事务实现、集群方案、主从复制原理、CAP和BASE理论以及负载均衡算法和类型。
一天五道Java面试题----第十天(简述Redis事务实现--------->负载均衡算法、类型)
|
2月前
|
算法 Go
[go 面试] 雪花算法与分布式ID生成
[go 面试] 雪花算法与分布式ID生成
|
6天前
|
机器学习/深度学习 JavaScript 算法
面试中的网红虚拟DOM,你知多少呢?深入解读diff算法
该文章深入探讨了虚拟DOM的概念及其diff算法,解释了虚拟DOM如何最小化实际DOM的更新,以此提升web应用的性能,并详细分析了diff算法的实现机制。
|
2月前
|
JavaScript 算法 索引
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
这篇文章深入分析了Vue中的diff算法,解释了其在新旧虚拟DOM节点比较中的工作机制,包括同层节点比较、循环向中间收拢的策略,并通过实例演示了diff算法的执行过程,同时提供了源码层面的解析,说明了当数据变化时,如何通过Watcher触发patch函数来更新DOM。
【Vue面试题二十三】、你了解vue的diff算法吗?说说看
|
2月前
|
算法
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
|
2月前
|
机器学习/深度学习 算法 数据中心
【机器学习】面试问答:PCA算法介绍?PCA算法过程?PCA为什么要中心化处理?PCA为什么要做正交变化?PCA与线性判别分析LDA降维的区别?
本文介绍了主成分分析(PCA)算法,包括PCA的基本概念、算法过程、中心化处理的必要性、正交变换的目的,以及PCA与线性判别分析(LDA)在降维上的区别。
51 4
|
2月前
|
算法
突击面试:解密面试官的算法题集合
突击面试:解密面试官的算法题集合
|
2月前
|
消息中间件 存储 算法
这些年背过的面试题——实战算法篇
本文是技术人面试系列实战算法篇,面试中关于实战算法都需要了解哪些内容?一文带你详细了解,欢迎收藏!
|
2月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
2月前
|
XML 存储 JSON
【IO面试题 六】、 除了Java自带的序列化之外,你还了解哪些序列化工具?
除了Java自带的序列化,常见的序列化工具还包括JSON(如jackson、gson、fastjson)、Protobuf、Thrift和Avro,各具特点,适用于不同的应用场景和性能需求。
下一篇
无影云桌面