Combinations

Combinations - LeetCode

접근 방법 [필수 작성]

제한조건 확인

• nCk 조합
• nCk 에서 가능한 최대 연산수는 얼마인가에 대한 고찰 (직관: nC(n/2) 정도 아닐까?)
• 20C10 값은? → 계산기 사용불가할때 이럴땐 시간복잡도를 어떻게 계한하지? → 대충 20^10 이라고 생각해보자 → 10^10이면 이미 시간초과??

코드 구현 [필수 작성]

# 5시 20분 시작 - 5시 35분 끝
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        candidate = []
        result = []

        def backtrack(start,candidate):

            if len(candidate) == k:
                #print(candidate)
                result.append(candidate[:])
                return 

            for i in range(start,n+1):
                candidate.append(i)
                backtrack(i+1,candidate)
                candidate.pop()
            
            return result
        
        return backtrack(1,candidate)

배우게 된 점 [ 필수 X ]

제출 눌렀는데 틀렸던 코드

# 5시 20분 시작 - 
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack():
            result = []
            candidate = []

            if len(candidate) == k:
                result.append(candidate)
                return 

            for i in range(1,n+1):
                candidate.append(i)
                backtrack()
                candidate.pop()
            
            return result
        
        return backtrack()

업데이트되는 변수는 전역변수로 활용

재귀함수가 실행될때 마다 candidate = [] 로 인해 계속해서 후보군 리스트가 초기화되어서 무한루프를 돌게됨. 업데이트 되는 후보군리스트나 결과리스트는 반드시 재귀함수 바깥으로 빼주어 전역변수로 만들어주는 것이 중요하다.

참조에 대한 이해

result.append(candidate)