N M9

문제 복기

N개의 자연수 중 M개를 선택하여 수열을 만든다. 이 때, N개의 자연수 중 같은 수가 2개 이상일 때, 중복되는 수열을 여러번 출력하지 않는다.

입출력 예제

알고리즘 생각

1. 수를 입력받아서 임시 배열에 저장하고, 같은 수(중복)를 제거 하여 새로운 배열을 하나 만들어준다.

2. 갯수를 저장하는 배열 : 같은 수가 2개이상 나오면 그만큼의 갯수를, 중복되지 않으면 1을 저장한다.

3. 1과 2를 이용하여 재귀함수를 구현한다. NM1, NM5와 비슷하지만, 갯수를 이용하여 한번 사용하면 갯수를 -1해주고 다 사용하면 +1하여 원상태로 만들어준다. 갯수가 0보다 클 때만 그 숫자(인덱스)를 사용할 수 있도록 조건을 걸어주면 한번 사용한 숫자는 사용하지 못하지만, 갯수가 2개 이상인 수는 한번 사용하여 갯수가 -1되었지만 여전히 0보다 크기 때문에 한번더 사용이 가능해진다!

잘못 생각한 부분

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

중복되는 수를 제거하여 새로운 배열을 만들어주었기 때문에 이 배열을 index가 중복되지 않게 수열을 만들면된다고 생각했다. 하지만 이렇게 되면 index가 중복이 되지 않기 때문에 마지막에 {9,9}는 수열이 나오지 않게 된다! =>9 에 해당하는 것에 "갯수"를 부여하여 한번 사용했더라도 한번 더 사용할 수 있게 한다!

ex) num = {1,7,9} => {1,7},{1,9},{7,1},{7,9},{9,1},{9,7}