순열, 조합 c++ [재귀를 이용한 풀이]

이번 글에선, c++ 에서 순열과 조합을 재귀를 통해 구현하는 포맷에 대해 알려드리겠습니다.

혹시 next_permutation을 통한 풀이가 궁금하시다면, 아래 글을 참고해주세요.

순열과 조합 (C++) — 코딩이랑 이것저것 (tistory.com)

순열과 조합 (C++)

 

1) 순열

 

nPm, 즉 n개의 값들 중, m개를 처럼 순서를 고려해서 선택한다.

ex: (1,2) != (2,1)

 

 

입출력 예시

4 2   //4P2
1234  //주어진 수: 1,2,3,4

12
13
14
21
23
24
31
32
34
41
42
43
12

 

예시 코드

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<string.h>
using namespace std;

int n, m; // nPm
string given; //입력으로 주어진 string
vector<string> ans_list; //given의 nPm 가짓수 저장.
int visit[1000];

//nPM
void per(int depth, string ans) {
	if (ans.size() == m) {
		ans_list.push_back(ans);
		return;
	}
	if (depth == given.size()) return;

	for (int i = 0; i < given.size(); i++) { 
		int num = (int)given[i];
		if (visit[num])continue;
		visit[num] = 1;
		per(depth + 1, ans + given[i]);
		visit[num] = 0;
	}

}


int main() {
	cin >> n >> m;
	cin >> given;
	per(0, "");

	for (auto aa : ans_list) { //순열 리스트 출력
		cout << aa << endl;
	}
	cout << ans_list.size() << endl;
}

여기선 주어진 숫자의 내역이 string으로 주어졌다는 가정에 구현했다.

 

 

2) 조합

nCm 즉, n개의 값 중 m개를 순서 상관 없이  뽑는 것

ex: (1,2) == (2,1)

 

예시 입출력

4 2 //4C2
1 2 3 4 //이번엔 vector<int> 로 int 1개씩 받는다.

3 4
2 4
2 3
1 4
1 3
1 2

 

예시 코드

#include<iostream>
#include<vector>
using namespace std;
//n과 m (5) 

vector<int> given;
vector<vector<int>> ans_list;
int n, m;

//nCm

void addAns(vector<int> v){
	ans_list.push_back(v);
}
void comb(vector<int> v, int depth) {
	
	if (v.size()==m) {//종료 조건 2:m개 찾기 완료
		addAns(v);
		return;
	}
	if (depth == given.size()) return; // 종료 조건 1: 리스트 마지막

	comb(v, depth + 1);

	v.push_back(given[depth]);
	comb(v, depth + 1);
}

int main() {
	
	cin >> n>>m;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		given.push_back(tmp);
	}
	vector<int> v;
	comb(v, 0);

	for (int i = 0; i < ans_list.size(); i++) {
		for (auto a : ans_list[i]) {
			printf("%d ", a);
		}
		printf("\n");
	}

}

여기선 주어진 숫자의 내역이 vector<int> 로 주어졌다는 가정에 구현했다.