###### 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:

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)