조합생성 (백트래킹)

문제

- n개의 숫자 중 k개를 선택하는 모든 조합을 찾습니다.

- 백트랙킹을 사용하여 가능한 모든 조합을 탐색합니다.

- 조합은 순서가 없으므로 [1,2]와 [2,1]은 같은 조합입니다.

 

입력

- n: 전체 숫자의 개수 (1부터 n까지)
- k: 선택할 숫자의 개수

 

출력

- 모든 가능한 조합의 리스트

 

예제 입력

n = 4, k = 2

 

예제 출력

출력: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

 

- 풀이 방법

현재 그림이 헷갈리게 되어 있는데, 그림 왼쪽의 n이 현재 def bactrack의 start이다.

 

위 방법처럼 1부터 3까지 진행을 쭉 하는데, [1,2] [2,1]은 같으므로 값이 올라갈수록 이전값보다 큰 값만 비교

result = []

def backtrack(start, current_combination):
        """
        백트랙킹 헬퍼 함수
        
        Args:
            start: 탐색을 시작할 숫자
            current_combination: 현재까지 선택한 숫자들
        """
        if len(current_combination) == k : 
            result.append(current_combination[:])
            return 
        for i in range(start, n+1) :
            current_combination.append(i)
            backtrack(i+1, current_combination)
            current_combination.pop()
    
    backtrack(1, [])
    return result