# 77. Combinations
#### Difficulty: Medium
link: https://leetcode.com/problems/combinations/

### 1. Backtracking
#### $O(C^{n}_{k})$ runtime, $O(C^{n}_{k})$ space

找出所有排列組合，用backtracking窮舉，path紀錄走過的路徑，。

每次選擇要或不要加入新的now_idx。
##### python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []

        def backtrack(now_ans, now_idx):
            if len(now_ans) == k:
                ans.append(now_ans)
                return
            if now_idx > n:
                return
            
            backtrack(now_ans+[now_idx], now_idx+1)
            backtrack(now_ans, now_idx+1)
        
        backtrack([], 1)

        return ans

避免重複，每次選擇low~n的數字。
##### python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        def backtracking(path, low):
            for i in range(low, n+1):
                if len(path) == k - 1:
                    result.append(path + [i])
                else:
                    backtracking(path + [i], i + 1)
        
        backtracking([], 1)
        return result

運用到函數本身的遞迴解法。
##### python

class Solution:
    def combine(self, n, k):
        if k == 0:
            return [[]]
        return [pre + [i] for i in range(k, n+1) for pre in self.combine(i-1, k-1)]

###### tags: `leetcode`