[백준] [Python] N과 M (4) - 백트래킹

www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

 

Python

n, m = map(int, input().split())


arr = [0]*(n+1)
result = []
def backtracking(level, k):
    if (k == m):
        result.append(arr[:m])
        return
    for i in range(level,n+1):
        arr[k] = i
        backtracking(i, k+1)
        #print(level, i, k, arr)

backtracking(1,0)

for x in result:
    for i in range(m):
        print(x[i], end=" ")
    print()

 

 

시간 초과

-> 오른쪽 사진보다 더 많이 출력됨

-> 중복 여부를 걸러내기 위한 절차와 같은 수가 쓰인 수열들도 계산하여 느려짐

-> for문의 시작을 무조건 1부터 하지 않고, 왼쪽에 적은 숫자부터 계산함으로써 오름차순으로 된 수열을 확인할 수 있을 뿐더러 불필요한 계산을 거치지 않아도 됨

n, m = map(int, input().split())


arr = [0]*(n+1)
result = []
def backtracking(k):
    if (k == m):
        x = arr[:m]
        x.sort()
        if x not in result:
            result.append(x)
        return
    for i in range(1, n+1):
        arr[k] = i
        backtracking(k+1)
        print(i,k,arr)

backtracking(0)

for x in result:
    for i in range(m):
        print(x[i], end=" ")
    print()