> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/n-m1.md).

# 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가 되고 아무런 영향 관계가 없기 때문이다!

**핵심이 되는 재귀 함수 부분**

```java
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;
}
```

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

![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-Ma6L-lV5INqok4sQhp0%2F-Ma6L6MHJ2_ICOIPW00P%2Fimage.png?alt=media\&token=4cd9b77b-258c-4245-b764-15b0d939c8b2)