#

# @lc app=leetcode.cn id=77 lang=python3

#

# [77] 组合

#

# https://leetcode-cn.com/problems/combinations/description/

#

# algorithms

# Medium (68.76%)

# Likes: 129

# Dislikes: 0

# Total Accepted: 13.2K

# Total Submissions: 19.1K

# Testcase Example: '4\n2'

#

# 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

#

# 示例:

#

# 输入: n = 4, k = 2

# 输出:

# [

# ⁠ [2,4],

# ⁠ [3,4],

# ⁠ [2,3],

# ⁠ [1,2],

# ⁠ [1,3],

# ⁠ [1,4],

# ]

#

#

class Solution:

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

def backtrack(first = 1, curr = []):

if len(curr) == k:

output.append(curr[:])

for i in range(first, n + 1):

curr.append(i)

backtrack(i + 1, curr)

curr.pop()

output = []

backtrack()

return output