[leetcode]77_组合_给定数字范围且输出无重复

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n

解题思路：【回溯】

回溯三部曲：
    1、确认递归函数返回值与参数：n,k，结果数组res，子集合path，子集合首元素起始位置startindex。
    2、回溯函数终止条件：找到长度为k的子集合。
    3、单层搜索过程：
        循环遍历[startindex, n + 1 - (k - len(path)) + 1]的每个元素i
        ——包含剪枝操作：
                从startindex开始，确保可以满足子集合还需要的元素数目k - len(path)；
                不满足，则结束循环遍历（不进行遍历）。
        path.append(i)，再递归遍历子集合下一元素startindex + 1；
        若子集合的遍历终止，则回溯path.pop()，遍历下一个元素i + 1。

class Solution:
    def combination(self, n, k, startindex, res, path=[]):
        length = len(path)
        if length == k:
            #   此处必须采用这种形式，表示将path中的元素添加到res中；
            #   若采用res.append(path)，表示将path引用添加到res中
            res.append(path[:])
            #   回溯，寻找下一组
            return
        #   循环遍历元素，并剪枝
        for i in range(startindex, n + 1 - (k - length) + 1):
            path.append(i)
            self.combination(n, k, i + 1, res, path)
            #   回溯
            path.pop()

if __name__ == '__main__':
    try:
        n, k = map(int, input().split())
        res = []
        solution = Solution()
        solution.combination(n, k, 1, res)
        print(res)
    except Exception as e:
        print(e)

仅作为代码记录，方便自学自查自纠