[Backtracking: Combinations] 77. Combinations

77. Combinations

 

https://youtu.be/q0s6m7AiM7o?si=im6vNN9SG6FK35Vs

 

풀이 과정

1. 문제 이해:
   • n: 1부터 n까지의 숫자.
   • k: 조합에 포함할 숫자의 개수.
   • 조합은 순서가 중요하지 않음.
2. 백트래킹 전략:
   • 숫자 1부터 n까지 반복하며 k개의 숫자를 선택.
   • 선택된 숫자는 조합에 추가.
   • 조합이 k개의 숫자를 만족하면 결과에 추가.
   • 선택한 숫자를 다시 되돌려가며 새로운 조합을 탐색.
3. 최적화:
   • 현재 숫자 iii를 선택한 뒤에는 i+1부터 탐색.
   • 중복된 조합 생성을 방지.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []  # 결과를 저장할 리스트

        # 백트래킹 함수 정의
        def backtrack(start, comb):
            # 종료 조건: 현재 조합의 길이가 k이면 결과에 추가
            if len(comb) == k:
				# comb의 복사본을 추가 
                res.append(comb[:]) // res.append(comb.copy()) 사용 가능 
                return
            
            # start부터 n까지 반복
            for i in range(start, n + 1):
                comb.append(i)  # 숫자 추가
                backtrack(i + 1, comb)  # 다음 숫자 탐색
                comb.pop()  # 선택한 숫자 제거 (백트래킹)

        # 백트래킹 시작
        backtrack(1, [])
        return res

 

코드 설명

1. res:
   • 가능한 조합을 저장하는 리스트.
2. backtrack 함수:
   • 매개변수:
     • start: 현재 탐색을 시작할 숫자.
     • comb: 현재 조합.
   • 종료 조건:
     • comb의 길이가 k가 되면 조합을 결과에 추가.
   • 반복:
     • 현재 숫자를 추가하고, 다음 숫자로 재귀 호출.
     • 재귀 호출 후 숫자를 제거(백트래킹).
3. 탐색 범위:
   • 1부터 n까지 숫자를 탐색.
   • 선택된 숫자 이후의 숫자만 탐색하여 중복 방지.

질문 1: 왜 복사본을 추가하나요?

복사본을 추가하는 이유는 **리스트가 가변 객체(mutable object)**이기 때문입니다.

백트래킹 과정에서 comb 리스트는 계속해서 추가(append) 및 제거(pop) 작업을 통해 조합을 구성합니다.

만약 복사본을 추가하지 않고 res.append(comb)를 사용하면, res에 저장된 값들이 나중에 변경될 수 있습니다.

 

질문 2: [1,2]와 [2,1]이 동일하게 간주되도록 처리하는 코드

[1,2]와 [2,1] 같은 조합은 순서를 고려하지 않으므로, 다음 두 가지 방식으로 중복을 방지합니다:

1. 탐색 시작 지점(start) 설정:
   • backtrack 함수에서 숫자 i 를 추가한 뒤, 다음 재귀 호출은 i+1 부터 시작합니다.
   • 이를 통해 이전에 탐색한 숫자보다 작은 숫자는 다시 탐색하지 않으므로, 순서가 다른 중복 조합이 생성되지 않습니다.
2. 코드 부분:

 

질문 3: 왜 set이 필요하지 않나요?

1. 백트래킹에서 중복 방지 설계:
   • 탐색 시작 지점 start를 매번 현재 숫자 다음(i+1)으로 설정합니다. 이 방식으로 숫자가 순서대로만 추가됩니다.
   • 결과적으로, 숫자의 순서가 다르더라도 같은 조합을 중복 생성하지 않습니다.
2. 순서 제한이 효과적으로 중복을 제거:
   • 조합 생성 시, 항상 작은 숫자에서 큰 숫자로 확장됩니다.
   • 예를 들어, n=4, k = 2의 경우:
     • [1, 2]는 생성되지만, [2, 1]은 생성되지 않습니다. 탐색 순서가 항상 증가 방향으로만 진행되기 때문입니다.
3. set을 사용하면 불필요한 오버헤드 발생:
   • set을 사용해 결과를 필터링하면 불필요하게 추가적인 메모리 사용과 연산이 발생합니다.
   • 현재 알고리즘은 순서를 제한해 이미 중복이 없으므로, set을 사용하지 않는 것이 더 효율적입니다.

 

요약

• 복사본을 추가하는 이유: 가변 객체의 변경으로 인한 결과값 변형을 방지하기 위해서.
• 순서를 고려하지 않는 조합 처리:
  • 탐색 시작 지점을 start로 제한하여 중복 조합 생성을 방지.

 

최종 코드

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 조합이므로 1부터 시작해서 n 까지
        # 부분집합 개수가 k 인것만..

        Comb = []  # 결과 조합을 저장할 리스트
        
        def help(i, CurComb, Comb, n, k):
            # 현재 조합(CurComb)의 길이가 k가 되면 결과에 추가
            if len(CurComb) == k:
                Comb.append(CurComb.copy())  # 현재 조합을 복사해서 추가
                return  # 더 이상 탐색하지 않고 리턴

            # i가 n보다 크면 더 이상 선택할 수 있는 숫자가 없음 → 종료
            if i > n:
                return

            # 현재 숫자 i를 조합에 포함시키는 선택
            CurComb.append(i)  # i 추가
            help(i+1, CurComb, Comb, n, k)  # 다음 숫자(i+1)부터 탐색
            CurComb.pop()  # 백트래킹: i를 제거하고 다음 분기 시도

            # 현재 숫자 i를 포함하지 않는 선택
            help(i+1, CurComb, Comb, n, k)  # i 건너뛰고 i+1부터 탐색

        help(1, [], Comb, n, k)  # 1부터 탐색 시작
        return Comb  # 최종 조합 리스트 반환