> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/bu-chong-2140-dao/77.-combinations.md).

# 77. Combinations

\# Medium

{% hint style="info" %}
Key idea: backtracking, 回溯法

不难
{% endhint %}

```python
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        comb = []
        sub = []
        nums = [i for i in range(1, n+1)]
        self.helper(nums, 0, k, comb, sub)
        return comb
        
    def helper(self, nums, i, k, comb, sub):
        # edge case
        if k == 0:
            comb.append(sub[:])
            return
            
        # regular case
        while i < len(nums):
            sub.append(nums[i])
            self.helper(nums, i+1, k-1, comb, sub)
            sub.pop()
            i += 1
```

Time complexity = $$O(A^k\_n)$$ , time complexity = $$O(A^k\_n)$$&#x20;