[C++] Combination(조합)

조합은 순서가 없이 몇개를 뽑느냐의 갯수를 샐떄 쓰인다.

nCr : n명중에 r명을 고른다. = nCr = n! / r!(n-r)!  

C++에서 이를 재귀 or 반복문으로 표현할 수 있다.

 

재귀버전

int n = 5, k = 3, arr[5] = { 1,2,3,4,5 };

void print(vector<int> v) {
	for (int i : v) {
		cout << i << ' ';
	}
	cout << endl;
}

void combi(int start, vector<int> v) {

	if (v.size() == k) {
		print(v);
		return;
	}
	for (int i = start + 1; i < n; i++) {
		v.push_back(i);
		combi(i, v);
		v.pop_back();
	}
}

int main() {
	vector<int> v;
	combi(-1, v);
}

 

반복문 버전

int main() {
	for (int i = 0; i < 5; i++) {
		for (int j = i+1; j < 5; j++) {
			for (int k = j+1; k < 5; k++) {
				cout << i << ' ' << j << ' ' << k << endl;
			}
		}
	}
}

 

출력결과 : 

조합 출력결과