本文讲述了python基础编程100例：第76期-基础算法：回溯 组合！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第76期-基础算法：回溯 组合

1 问题描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入: n = 4, k = 2

输出:

[

[2,4],

[3,4],

[2,3],

[1,2],

[1,3],

[1,4],

]

输入: n = 1, k = 1

输出: [[1]]

初始代码

from typing import List

class Solution:

    def combine(self, n: int, k: int) -> List[List[int]]:

        #在此之间填写代码

print(Solution().combine(4,2))

print(Solution().combine(1,1))

2 解题思路

标签：回溯

如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；

回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；

组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。

3 解题方法

from typing import List

class Solution:

    def combine(self, n: int, k: int) -> List[List[int]]:

        res,path=[],[]

        m=list(range(1,n+1))

        def backtrack(a,res,path,k):

            if k==0:

                res.append(path[:])

            x=len(a)

            for i in range(x):

                b=a.pop(i)

                path.append(b)

                backtrack(a[i:],res,path,k-1)

                path.pop()

                a.insert(i,b)

        backtrack(m,res,path,k)

        return res

print(Solution().combine(4,2))

print(Solution().combine(1,1))

第1-3，19-20行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义列表res、path分别用于存放每个组合和组合中的数字

第5行： 定义变量m并赋值从1到n的列表

第6行： 创建backtrack回溯函数，内部变量初始列表以及后面要求的列表以及限制条件

第7-8行： 当k=0时，说明此时path里面元素的数量已经满足条件了，将其放进res列表中

第9-10行： 定义变量x用于存放初始列表长度用于之后的for循环遍历列表元素

第11行： 定义变量b，从初始列表中删除第一个元素并赋值给b

第12行： 在path列表中添加该元素

第13行： 使用backtrack函数对剩余的列表进行相同操作

第14-15行： 回溯操作的回溯，返回

第9-10行： 定义变量x用于存放初始列表长度用于之后的for循环遍历列表元素

第11行： 定义变量b，从初始列表中删除第一个元素并赋值给b

第12行： 在path列表中添加该元素

第13行： 使用backtrack函数对剩余的列表进行相同操作

第14-15行： 回溯操作的回溯，返回迭代之前的元素，对下一个元素进行操作

第16行： 函数定义完成，开始运行函数

第17行： 返回最后的res

代码运行结果为：

算法讲解

这里用到了基础算法：回溯，简单讲解下这个算法：

回溯

回溯是很经典的一个算法，什么是回溯，回溯其实是一种暴力枚举的方式，为啥都暴力了还是很经典的一种方法呢，其实是因为有些问题我们能暴力出来就不错了，就别要其他自行车了。常见的回溯类问题：组合；排列；切割；子集；棋牌；

其实回溯算法就是常说的DFS,本质上是一种暴力枚举算法；

回溯算法常用于解决的问题：

组合

排列

切割

子集

棋盘：N皇后

比如最经典的排列。从1,2,3,4,5中取3个数组成排列有多少种，我们肯定会解决这种问题，但是程序怎么写呢。想一下我们解决这个问题的过程，我们先选1，然后第二个数可以选2，第三个数可以选3，这是一种答案了，然后呢，换第三个数，第三个数选4，又一种答案，再换，第三个数选5，没得选了，所以以12打头的数都选完了，得到三种答案.然后再换第二个数，第二个数选3，然后第三个数选4，注意是组合问题所以我们不能退往回选2了，不然就重复了。就是这样一种选择方案，一直到第3个数选成了3，得到答案345，就不用往后进行了。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。