组合
题解:
1.递归方法的参数以及返回值
从示例中我们可以看出,需要定义两个列表变量,一个用来存放符合条件的单一结果,另一个存放符合条件结果的集合
方法的参数一定要有整数n 和 k,还需要一个变量startindex,用来记录本层递归中,集合从哪里开始遍历,防止出现重复的组合
方法如下:
def backtracking(n, k, startindex)
无返回值
2.终止条件
path数组的大小达到k,说明找到了一个子集大小为k的组合
if len(path) == k:
result.append(path[:])
return
3.单层搜索过程
回溯法的搜索过程就是一个树形结构的遍历过程,在如下图中,可以看出for循环用来横向遍历,递归的过程是纵向遍历,因此for循环每次从startindex开始遍历,然后path用来保存取到的值
代码:
代码中有个剪枝的操作,前面题解中说明到变量startindex,他是用来记录本层递归开始遍历的地方,当我们for循环选择的起始位置之后的元素已经不足我们需要的元素个数了,就没有必要搜索了