💡 백트래킹
Memory 2064KB Time 24ms Code Length 710B
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) {
if (depth == M) {
for (auto i : vc) {
cout << i << " ";
}
cout << '\n';
return;
}
for (int i = 0; i < nums.size(); i++) {
if (visited[nums[i]]) continue;
visited[nums[i]] = 1;
vc.push_back(nums[i]);
dfs(depth + 1);
vc.pop_back();
visited[nums[i]] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
init();
dfs(0);
}
이 코드는 입력으로 최대 숫자 N과 갯수 M을 받고, N개의 숫자를 입력받아 정렬한 뒤, M개의 숫자를 선택하는 모든 경우의 수를 출력하는 프로그램이다.
init() 함수에서는 N과 M을 입력받고, N개의 숫자를 입력받아 정렬한 뒤, cnt를 0으로 초기화한다.
dfs() 함수는 재귀적으로 숫자를 선택하는 함수이다. depth가 M과 같아지면 선택한 숫자들을 출력하고, 그렇지 않은 경우에는 숫자를 선택하고 재귀적으로 다음 숫자를 선택하는 과정을 반복한다. 선택한 숫자는 vc에 저장되고, 이미 선택한 숫자는 visited 배열을 통해 체크된다.
main() 함수에서는 입력을 받고, init() 함수를 호출한 뒤 dfs(0)을 호출하여 숫자 선택 과정을 시작한다.
