[BackTracking 문제] Leetcode 77. Combinations

문제

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

상기 문제는 주어진 문자를 회문(Palindrome)으로 변환하기 위한 최소한의 문자를 판단하여 추가하는 문제이다.

문제풀이

문제 1 : Backtracking 방식(속도 약 20%)
class Solution(object):
    def combine(self, n, k):
        result=[]
        queue=deque()
        def dfs(start,queue,k):
           # print(start,queue,k)
            if k==0:
                result.append(list(queue))
                return
            for i in range(start+1,n+1):
                queue.append(i)
                dfs(i,queue,k-1)
                queue.pop()
        dfs(0,queue,k)
        return result
 
#풀이 2 : 내장함수(98% 속도) 
from itertools import combinations
class Solution(object):
    def combine(self, n, k):
        a= [i for i in range(1,n+1)]
        return list(combinations(a,k))
        

Lookback

1. 이번 문제는 백트래킹 혹은 내장함수 combinations을 통해 해결 가능한 문제였다. 다만 내부 함수의 경우 속도 부문에서 효율적이었는 데 Cpython이라고 불리는 파이선의 기본 구현에서 C언어로 작성되었기 떄문으로 확인하였다. (/Modules/itertoolmodule.c파일 내 구현됨)