[c++] N과 M(9) (15663), 백트래킹, 재귀, DFS

문제 https://www.acmicpc.net/problem/15663

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1
4 4 2

예제 출력 1 복사

2
4

예제 입력 2 복사

4 2
9 7 9 1

예제 출력 2 복사

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

풀이

• 입력 숫자들에 중복된 수가 포함될 수 있으므로 주의해야 함
• 인덱싱을 기준으로 재귀를 수행하면, 중복되는 수열이 출력됨
• 오름차순으로 정렬 후에 중복되는 수를 제외하고 수열 생성, 인접한 수에 중복된 수가 있으므로 이전 값을 저장해놓고 다음 값과 같으면 수행하지 않도록 해야 함.

 

코드

• 트리 구조에서 각 상태를 생각
• 상태에서의 이전 값을 tmp로 저장해서 중복을 피하도록 구성한다.
• 재귀에서 돌아오면 이전에 저장한 tmp로 인해 다음 중복된 수를 피할 수 있음.
• + sort()로 이미 오름차순 정렬되었기 때문에 중복된 수는 인접한다.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/10.%20%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9/N%EA%B3%BC%20M(9)%20(15663).cpp