[C++] 조합

조합: n 개의 원소를 갖는 집합에서 m (n 이하의 자연수)개를 선택하여 만드는 부분집합

1. 순서를 따지지 않고, 중복을 허용하지 않음. (순서X, 중복X)
2. 반복문을 돌며, 모든 경우에 대해 선택한다.
3. 반복문의 시작 값은 이전에 선택한 값 + 1이 된다.

1. 순열(permutation) 특징 활용하기

🔗 [C++] 순열

✏️ 예시

for (int i = 1; i <= len; i++) {
		vector<bool> v(len - i, false);
		v.insert(v.end(), i, true);
		//i개
		do {
			string temp = "";
			for (int k = 0; k < len; k++) {
				if (v[k]) temp += s[k];
			}
			cout << temp << endl;
		} while (next_permutation(v.begin(), v.end()));
		cout << endl;
	}

• vector v : 부분집합에 추가한 원소인지 확인하기 위한 visited vector
• permutation 알고리즘에서 for 문으로 개수가 다를 경우를 모두 출력하는 형식

2. DFS 사용하기

✏️ 예시 code
1, 2, 3, 4에 대해 3개씩 조합

int cArr[r] = { 0, };

void comb(int depth, int next){
    if(depth == r){
        printArray(cArr);	//3개 조합이 끝나면 출력하기 
        return;
    }

    for(int i = next; i <= n; i++){
        cArr[depth] = i;
        comb(depth + 1, i + 1);
    }
}

int main(void){

    comb(0, 1);

    return 0;
}

next : 시작하는 값 or index
r : 조합 개수
n : 조합 대상 벡터 or 배열의 size

mCn 조합 만들기

✏️ 예시 code

int ans = 1;
int r = 1;
for (int i=m; i > m-n; i--) {
	ans *= i;
    ans /= r++;
}

4. 조합 결과 중에 long long 형의 범위를 넘는 결과가 있는 경우

⭐️ 파스칼의 삼각형 원리 사용 ➡️ mCn = m-1Cn-1 + m-1Cn

참고 문제
🔗 [BOJ/C++] 2407: 조합