[LeetCode] 77. Combinations

Problem : https://leetcode.com/problems/combinations/

Equivalent to traverse a tree constructed with number 1 ~ n. On each step the code may chose pick or not pick the number on this step.

Time Complexity : O ( N * (N - 1) .. (N-K) ) 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            if x <= n:
                # pick x
                backtrack(x+1, partial + [x])
                
                # not pick x
                backtrack(x+1, partial)
            
        backtrack(1, [])
        return result
        

Another backtracking solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def backtrack(x, partial):
            if len(partial) == k:
                result.append(partial)
                return
             
            for i in range(x, n+1):
            	# pick number i
                backtrack(i+1, partial + [i])
                # not pick number i
            
        backtrack(1, [])
        return result

BFS solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if k == 0: return []
        if k == n: return [[i+1 for i in range(n)]]
                   
        result = []
        queue = deque([[i+1] for i in range(n)])
        
        while queue:
            combo = queue.popleft()
            
            if len(combo) == k:
                result.append(combo)
            else:
                for i in range(combo[-1] + 1, n+1):
                    queue.append(combo + [i])
        
        return result