---
# System prepended metadata

title: 77. Combinations
tags: [Leetcode, medium, python, backtracking]

---

###### tags: `Leetcode` `medium` `backtracking` `python`

# 77. Combinations

## [題目連結:] https://leetcode.com/problems/combinations/

## 題目:
Given two integers ```n``` and ```k```, return all possible combinations of ```k``` numbers chosen from the range ```[1, n]```.

You may return the answer in **any order**.


**Example 1:**
```
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.
```
**Example 2:**
```
Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.
```

## 解題想法:
* 題目為: 給n、k
    * 求數字 1 ~ n 去組合長度為 k 的所有可能
* 遞歸求解:
    * dfs每次傳遞:
        * n: 範圍
        * k: 剩餘可用的長度
        * cur_val: 目前開始數字
        * path: 當前數組list
    * 若k==0:
        * 則path可加入到最終res

## Python:
``` python=
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        self.res=[]
        self.dfs(n,k,1,[])
        return self.res
    def dfs(self,n,k,cur_val,path):
        if k==0:
            self.res.append(path)
            return 
        for i in range(cur_val,n+1):
            self.dfs(n,k-1,i+1,path+[i])

result = Solution()
n = 4
k = 2
ans = result.combine(n,k)
print(ans)
```