💡 백트래킹
Memory 2064KB Time 0ms Code Length 725B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N, M; // 최대숫자, 갯수
vector<int> nums;
void init() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
int num;
cin >> num;
nums.push_back(num);
}
sort(nums.begin(), nums.end(), less<int>());
int cnt = 0;}
vector<int> vc;
int visited[10001];
void dfs(int depth,int idx) {
if (depth == M) {
for (auto i : vc) {
cout << i << " ";
}
cout << '\n';
return;
}
for (int i = idx; i < nums.size(); i++) {
if (visited[nums[i]]) continue;
visited[nums[i]] = 1;
vc.push_back(nums[i]);
dfs(depth + 1, i);
vc.pop_back();
visited[nums[i]] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
init();
dfs(0,0);
}
이 코드는 주어진 숫자들 중에서 M개를 선택해 만들 수 있는 모든 조합을 출력하는 프로그램이다.
init 함수에서는 N과 M을 입력받고, N개의 숫자를 입력받아 정렬한 뒤에 저장한다.
dfs 함수는 재귀적으로 숫자를 선택하며, 선택된 숫자들을 vc 벡터에 저장하고, depth가 M이 되면 해당 조합을 출력한다.
이때, visited 배열을 사용하여 이미 선택된 숫자를 다시 선택하지 않도록 하며, 모든 조합을 출력한다.
main 함수에서는 초기화(init)를 수행한 뒤, dfs 함수를 호출하여 모든 조합을 출력한다.
