[DFS]77. Combinations

• 分类：DFS
• 时间复杂度: O(nk)*

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

代码：

class Solution:
    def combine(self, n: 'int', k: 'int') -> 'List[List[int]]':
        res=[]
        my_list=[]
        self.dfs(n,k,1,my_list,res)
        return res
    
    def dfs(self,n,k,start,my_list,res):
        if k==0:
            res.append(my_list.copy())
        for i in range(start,n+1):
            my_list.append(i)
            self.dfs(n,k-1,i+1,my_list,res)
            my_list.pop()

讨论：

1.这个时间复杂度让我有点晕