[ 백트래킹 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M, input;
int arr[10];
bool isused[10];
vector<int> save(10);
void func(int depth){
if(depth == M){
for(int i=0;i<M;i++)
cout << arr[i] << ' ';
cout << '\n';
}else{
for(int i=0;i<N;i++)
{
if(isused[i]) continue;
isused[i] = true;
arr[depth] = save[i];
func(depth+1);
isused[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
cin >> save[i];
sort(save.begin(), save.begin()+N);
func(0);
return 0;
}
- 수가 정해져 있기 때문에
save
변수를 쓰는데, 사전순 증가로 출력해야 하기 때문에 정렬하려고 vector<int> save
로 선언
[ next_permutation 코드 ]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
int arr[10];
vector<int> save(10);
vector<vector<int>> ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
cin >> save[i];
sort(save.begin(), save.begin()+N);
fill(arr, arr+N, 1);
for(int i=0;i<M;i++) arr[i] = 0;
do{
vector<int> tmp;
for(int i=0;i<N;i++)
if(!arr[i]) tmp.push_back(save[i]);
do{
ans.push_back(tmp);
}while(next_permutation(tmp.begin(), tmp.end()));
}while(next_permutation(arr, arr+N));
sort(ans.begin(), ans.end());
for(auto a : ans)
{
for(auto b : a)
cout << b << ' ';
cout << '\n';
}
return 0;
}
next_permutation()
을 2중으로 써야함
1) 전체 N개에서 M개를 뽑은 숫자들 구하는 do~while
2) 뽑은 M개 숫자에 대해 다시 경우의 수를 구하는 do~while
vector<vector<int>> ans
에 대해 오름차순 정렬하면
요소별로 비교해서 정렬됨!