N M1

문제 설명 : 1부터 N까지 자연수 중 중복없이 M개를 골라 수열을 만든다. 사전 증가순으로 출력해라.

알고리즘 생각

1. 필요한 자료구조 : 중복 체크를 하기 위해 boolean 배열, 수열을 저장하기 위한 int 배열

2. 수열 배열을 0부터 m-1까지 index번째 수를 채운다. a[index] = x, index = index+1, x는 사전 증가순 출력이기 때문에 1부터 시작, n까지 가능 넣은 x를 다음에 선택할 땐 빼기 위해 c[x] = true로 기록해준다.

3. index+1번째 수를 결정하기 위해 재귀함수로 호출하면 중복체크 c배열에서 사용 가능한 정수를 확인할 수 있고, 1부터 체크하여 사용하지 않은 수가 나오면 그 수를 index+1에 넣는다.

4. for문 i=1~n까지 다 돌고나면 돌아와서 c[i] = false;처리를 꼭 해준다! 그렇지 않으면 앞자리 수로 돌아갔을 때 모든 수가 true로 되어 선택 가능한 수가 없게 되기 때문이다! =>어 그럼 이미 사용한 수인데 false 처리하면 다시 이 수를 사용하는 것으로 되면 어떻하나 하는 염려는 필요없다. 왜냐하면 index번째 수를 채울 때 i는 1부터 1씩 증가하기 때문에, index번째에 i=3을 채우고나서 c[i=3] = false처리를 하고 나면 i=4가 되고 아무런 영향 관계가 없기 때문이다!

핵심이 되는 재귀 함수 부분

for(int i=1;i<=n;i++) {
	if(c[i]) continue;
	c[i] = true;a[index] = i;
	go(index+1,n,m);
	c[i] = false;
}

재귀함수 실행 순서(흐름)