0. 링크
1. 설명
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.
입출력 예시
| input | output |
|---|---|
3 1 | 1 2 3 |
4 2 | 1 2 1 3 1 4 2 3 2 4 3 4 |
2. 해설
M개의 수를 갖는 순열을 만들기 위한list벡터 선언Backtracking()함수 내에서 아래와 같이 반복한다.1)
list.size() == m이면return후 출력
2)i = count; i <= N인 동안 다음을 반복한다.(1)
list.push_back(i)
(2)Backtracking( i + 1 )
// 2와i = count로list[0]보다 작거나 같은 것은list에 올 수 없음을 보장한다.
(3)list.pop_back()
3. 코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector <int> list;
void print()
{
for (size_t i = 0; i < list.size(); i++)
{
cout << list[i] << " ";
}
cout << '\n';
}
void Backtracking(int count)
{
if (list.size() == m) {
print();
return;
}
for(size_t i = (size_t)count; i <= n ; i++)
{
list.push_back(i);
Backtracking(i + 1);
list.pop_back();
}
}
int main()
{
cin >> n >> m;
Backtracking(1);
}
4. 감상
앞의 N과 M (1)과 같은 유형의 문제다. 다른 점은 1번은 순열이고, 2번은 조합의 문제였다. 순열애서는 visited 벡터가 쓰였다. 조합에서는 자신과 자신보다 작은 수는 검사하지 않기 위해 Backtracking()에서 인자 count를 받아서 사용했다. 다음은 중복을 허용하는 순열이다!
