LeetCode 77. Combinations

파이썬 알고리즘 인터뷰 문제 35번(리트코드 77번) Combinations
https://leetcode.com/problems/combinations/

나의 풀이1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def helper(path, n, k):
            if len(path) == k:
                result.append(path)
                return
            for num in range(1, n + 1):
                if not path or path[-1] < num:
                    helper(path + [num], n , k)

        result = []
        helper([], n, k)
        return result

나의 풀이2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def helper(path, num):
            if len(path) == k:
                result.append(path[:])
                return
            if num <= n:
                helper(path, num + 1)
                path.append(num)
                helper(path, num + 1)
                path.pop()

        result = []
        helper([], 1)
        return result

나의 풀이3

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def helper(path, start):
            if len(path) == k:
                result.append(path[:])
                return
            for num in range(start, n + 1):
                path.append(num)
                helper(path, num + 1)
                path.pop()

        result = []
        helper([], 1)
        return result

나의 풀이4

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def helper(start, k, path):
            if k == 0:
                result.append(path[:])
                return
            for num in range(start, n + 2 - k):
                path.append(num)
                helper(num + 1, k - 1, path)
                path.pop()
        
        helper(1, k, [])

        return result

백트래킹 시리즈를 한번에 풀고, 잊을만 하면 다시 한번에 풀고를 반복해서 조금씩 풀이가 나아지고 있다.