[Algorithm] 수열 추측하기 (순열, 파스칼 응용)

## 수열 추측하기(순열, 파스칼 응용)


def DFS(L, sum):
    if L == n and sum == f:
        for x in p:
            print(x, end=' ')
        sys.exit(0)
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                p[L] = i
                DFS(L+1, sum+(p[L]*b[L]))
                ch[i] = 0



n, f = map(int, input().split())
b = [1]*n
p = [0]*n
ch = [0]*(n+1)

for i in range(1, n):
    b[i] = (b[i-1]*(n-i))//i

DFS(0, 0)

b 리스트를 구하는 것이 관건이다.
조합(combination)을 응용하여 b 리스트를 만들어야 한다.

DFS 함수 내에서는 중복을 체크하기 위해 ch 리스트를 사용하여 현재 사용한 i 값에 1을 넣었다.
그리고 좀 헷갈린 부분.. p[L] 이여야 하는데 p[i]로 써서 틀렸었다.
만약 n=4 일 때, p = [?, ?, ?, ?] 이고 인덱스는 0, 1, 2, 3 이므로 i가 들어올 수 없다. i는 1, 2, 3, 4 로 for문을 돌리기 때문!
따라서 L을 넣야 한다.