조합 구하기

문제

조합 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그
램을 작성하세요.

▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.

▣ 입력예제 1
4 2

▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6

---

풀이

def DFS(L, s):
    global cnt
    if L==m:
        for j in res:
            print(j, end=' ')
        cnt+=1
        print()
    else:
        for i in range(s,n+1):
            if ch[i]==0:
                ch[i]=1
                res[L]=i
                DFS(L+1,i+1) #s+1이 아니라 i+1임
                ch[i]=0

if __name__=="__main__":
    cnt=0
    n,m=map(int, input().split())
    ch=[0]*(n+1)
    res=[0]*m
    DFS(0, 1)
    print(cnt)

-DFS(L, s)

L: Level 층위

s: start 가지의 머리 부분을 의미한다.

-

else:

        for i in range(s,n+1):

            if ch[i]==0:

                ch[i]=1

                res[L]=i

                DFS(L+1,i+1) #s+1이 아니라 i+1임

                ch[i]=0

DFS(L+1, s+1)로 코드를 잘못 작성했었음-->틀린 코드

s부터 n까지를 i에 대입해서 돌리고 있으므로 i를 대입해야 한다. s는 고정값이다. 범위에 맞는 모든 값을

넣어야 하기 때문에 i+1로 대입해야 한다.

4, 2 입력값일 때 노드