p.346 35번 조합 더 효율적인 풀이

[DoTheBestMayB]

itertools 모듈을 사용하지 않고 풀이1 보다 실행 시간이 더 짧은 코드를 작성해봤습니다.

리트코드에서 풀이1은 412ms, 제가 작성한 코드는 92ms가 소요됩니다.

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        # depth 는 재귀적으로 불린 횟수 번호를 의미합니다.
        # 예를들어 dfs 를 처음 부르면 depth 는 1이고, 더 이상 재귀를 하지 않으면 원소가 1개인 결과 생성
        # depth 가 2이고, 더 이상 재귀를 부르지 않으면 원소가 2개인 결과 생성
        # depth 와 필요한 원소의 갯수인 k 를 비교해서 재귀 호출에 제한을 만들었습니다.
        def dfs(num_range: int, depth: int):
            if depth > k:
                return
            res = []
            # k 개의 조합을 만들어야 하는데 처음 숫자값이 k 보다 작을 경우, k개의 조합이 생성될 수 없음
            # ex) k=4, 시작 숫자가 3 일 경우, (3, 2, 1) ... 숫자가 부족함
            # 재귀적으로 호출되는 점을 고려해서 이것을 k-depth 로 구현함
            for num in range(num_range, k-depth, -1):
                sub_res = dfs(num-1, depth+1)
                if sub_res:
                    for sub_list in sub_res:
                        sub_list.append(num)
                        res.append(sub_list)
                else:
                    res.append([num])
            return res
        return dfs(n, 1)


ans = Solution.combine(Solution(), 4, 2)

print(ans)

[likejazz]

좋은 풀이네요. 감사합니다. 효율적인 풀이로 깃헙에 추가하도록 하겠습니다.