旭的小窝

77. Combinations

 
  • 2023年 06月11日

Promble

link: https://leetcode.com/problems/combinations/description/

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.

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.

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Approach 1

use itertools libs. 📓 this method only need 92 ms, and beats 90.32%.

Thought

  1. from itertools import combinations
  2. def nums = list(range(1, n+1))
  3. return list(combinations(nums, k))

Code

from itertools import combinations 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        nums = list(range(1, n+1))
        return list(combinations(nums, k))

Approach 2

DFS method.

Thought

  1. def results:list to store the final result.
  2. def DFS function
    1. var: n:int, k:int, index:int, comb:list, results:list.
    2. n is the length of list, k is the combination length, index is the currecnt index, comb is prepared add to result, results is the final results.
    3. if len(comb) == k: results.append(list(comb)) return # pruning
    4. loop i in (index+1, n+1)
      1. if n-i+1 < k-len(comb) return # when finded i cant larger than k, return
      2. comb.append(i)
      3. recurrence, self.dfs(n, k, i, comb, results)
      4. comb.pop(), pop the first num in comb, aka the prev status in the comb.

Code

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        self.dfs(n, k, 0, [], results)
        return results 

    # comb is prepared to add into results
    # index to loop the range(1,n+1)
    # restuls to store the final result
    def dfs(self, n, k, index, comb, results):
        # pruning 
        if len(comb) == k:
            results.append(list(comb))
            return 
        
        # loop i in (index+1, n+1)
        for i in range(index+1, n+1):
            # pruning, if later not comparet k, drop
            if n-i+1 < k - len(comb):
                return 
            comb.append(i)
            self.dfs(n, k, i, comb, results)
            comb.pop()
搜索