0077._combinations.md

77. Combinations

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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],
]

解题方案

思路 1 - 时间复杂度: O(n * n! / ((n-k)! * k!))- 空间复杂度: O(N)******

python作弊法,beats 98.15%

class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        return [list(i) for i in itertools.combinations(range(1,n+1), k)]

思路 2 - 时间复杂度: O(n * n! / ((n-k)! * k!))- 空间复杂度: O(N)******

从1开始，每次有两个选择

1. 取1，从后面的n-1个数中取k-1个数
2. 不取1，从后面的n-1个数中取k个数

DFS, beats 62.00%

class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        def dfs(cur_nums, idx):
            if len(cur_nums) == k:
                self.res.append(cur_nums)
                return
            if idx == n + 1:
                return
            dfs(cur_nums+[idx], idx+1)
            dfs(cur_nums, idx+1)
        self.res = []      
        dfs([], 1)
        return self.res

思路 3 - 时间复杂度: O(n * n! / ((n-k)! * k!))- 空间复杂度: O(N)******

递归, beats 92.45%

class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        # k = n的时候必须要直接return了，否则后面的self.combine(n-1, k)会runtime error
        if k == n or k == 0: 
            return [[i for i in range(1, k+1)]]
        res = self.combine(n-1, k-1) # select n
        res = [lst+[n] for lst in res]
        res.extend(self.combine(n-1, k)) # add the result of condition: not select n
        return res