백준 6603번 : 로또

[문제 링크] - https://www.acmicpc.net/problem/6603

6603번: 로또

N과 M 유형의 백트래킹 문제입니다.

단, 중복된 수를 뽑아서는 안되며 로또번호를 오름차순으로 나열해야 한다는 점만 유의하시면 되는 문제입니다.

정답 코드 (Python)

S = []
lottery = [0] * 13
visited = []

def backTrack(depth):
    global S
    if depth == 6:
        for i in range(6):
            print(lottery[i], end=' ')
        print()

    for i in range(len(S)):
        # S[i] not in visited : 중복선택 방지용 로직
        # S[i] > lottery[depth - 1] : 현재 숫자가 이전에 선택한 번호보다 큰지 확인하는 로직
        if S[i] not in visited and S[i] > lottery[depth - 1]:
            lottery[depth] = S[i]
            visited.append(S[i])
            backTrack(depth + 1)
            lottery[depth] = 0
            visited.pop()

while 1:
    temp = list(map(int, input().split()))
    if temp[0] == 0:
        break
    S = temp[1:]
    backTrack(0)
    print()