#include <stdio.h>
int n, r, cnt = 0;
int a[17];
int ch[17];
int res[17];
using namespace std;
void DFS(int x)
{
if(x == r)
{
for(int i = 0; i < r; i++)
printf("%d ", res[i]);
printf("\n");
cnt++;
}
else
{
for(int i = 1; i <= n; i++)
{
if(ch[i] == 0)
{
ch[i] = 1;
res[x] = a[i];
DFS(x+1);
ch[i] = 0;
}
}
}
}
int main()
{
scanf("%d %d", &n, &r);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
DFS(0); // 2번 설명
printf("%d", cnt);
return 0;
}1. 입력할 숫자의 개수 n, 뽑을 숫자의 개수 r, 입력된 숫자를 저장할 배열 a, 그 숫자가 쓰였는지 확인할 배열 ch, r개의 숫자를 저장했다가 출력하기 위한 배열 res를 전역변수로 선언한다. 배열의 원소를 0으로 초기화하고 DFS() 재귀함수에서 사용하기 위함이다.
n = 4
r = 3
a = [ 1, 3, 6, 7 ]
ch = [ 0, 0, 0, 0 ]
res = [ 0, 0, 0, 0]
2. DFS(int x) 에서 x는 깊이를 의미한다. 트리의 깊이가 r이 된다면 r개의 숫자를 뽑았다고 판단할 수 있다. 따라서 시작은 숫자를 뽑지 않았으므로 0으로 시작한다.
3. x 가 0에서 증가할 때
- 첫 번째 숫자가 쓰였는지 확인한다.( i = 1 ) ch[i] = 0 이기 때문에 쓰인 적이 없으므로 ch[i] = 1로 해주고 배열 a의 첫 번째 원소인 a[1] 을 res의 x 번째에 넣어준다. 여기서 res의 x 번째에 넣는 이유는 x 레벨(깊이)의 노드의 번호이기 때문이다. res에 값을 할당하고나면 다음 깊이를 탐색하기위해 DFS(x+1)을 한다.
4. x 가 r 이 될 때
- 깊이가 r이 되었다는 것은 r개만큼 숫자를 뽑았다는 의미이다. 문제에서 지나간 노드 번호를 출력하라고 했으므로 배열 res를 순회하면서 원소를 출력하고 줄바꿈을 해준다. 이 때 경우의 수 1개를 찾았으므로 cnt++을 한다.
