백준 1038 감소하는 수

백트래킹을 이용하는 문제이다.
백트래킹만 잘 구현한다면 문제를 쉽게 해결할 수 있다.

가능한 경우의 수가 엄청 크지않아 조합을 이용해 감소하는 수 배열을 만든 뒤, 정렬을 해도 된다.
하지만 경우의 수가 엄청 큰 문제에서는 위의 해결방법이 먹히진 않을 것 같고, 백트래킹을 사용해 순서대로 배열에 집어 넣었다.
자리수의 상한을 기준으로 백트래킹 탈출 조건을 만들고 제일 마지막 자릿수보다 작은 수들을 넣어 탈출조건으로 수렴하게 해주었다.

arr = []
def make(digit,number):
    if digit == 1:
        arr.append(number)
    for i in range(number%10):
        make(digit-1, number*10+i)
for i in range(10):
    for j in range(10):
        make(i+1,j)
n = int(input())
print(-1) if len(arr) <= n else print(arr[n])