题解 | #牛棚分组#

• 题目考察的知识点 : 递归和回溯算法
• 题目解答方法的文字分析: 核心思想是使用回溯算法，在生成符合要求的牛的组合方案时，每次都选择添加当前牛或不添加当前牛，并判断当前已经添加的牛数量是否满足要求。如果满足要求，则保存当前的组合方案，然后进行回溯（即删除最近添加的牛），继续向下遍历。当所有可能的组合方案都被遍历完后，返回包含所有符合要求的组合方案的列表。
• 本题解析所用的编程语言 :python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @param k int整型
# @return int整型二维数组
#
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def dfs(path, x, u):
            if u == 0 or x > n:
                if x <= n + 1 and u == 0:
                    res.append(path[:])
                return
            path.append(x)
            dfs(path, x + 1, u - 1)
            path.pop()
            dfs(path, x + 1, u)

        dfs([], 1, k)
        return res