[BOJ]15655번: N과 M(6)

<출처: https://www.acmicpc.net/problem/15655>

 

조합 문제입니다.

 

combination(idx + 1, cnt)

combination(idx + 1, cnt + 1)

위 코드 두 줄의 의미가 가장 중요합니다.

idx: 배열의 숫자 중 탐색을 수행할 인덱스 번호
cnt: N개 중 현재 몇 개를 뽑았는지

조합은 특정 숫자에 대해 뽑을지/말지를 결정합니다.

그러므로 매 깊이마다 최대 2개로 뻗어나갈 수 있습니다.

이를 통해 특정 숫자 num[idx]를 뽑을 수 있다면,

특정 숫자를 뽑는 combination(idx+1,cnt+1)과 뽑지 않는 combination(idx+1,cnt)을 모두 수행하고,

특정 숫자가 이미 사용되어 뽑을 수 없다면 뽑지 않는 combination(idx+1,cnt)만 수행해줍니다.

 

 

<코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ15655.cpp>