c++로 조합 구현하기

📌 1. 조합이란?

N개의 원소 중에서 중복 없이 순서를 고려하지 않고 K개를 고르는 경우의 수.

​

ex) {A, B, C, D} 중에서 2개를 고르면: AB, AC, AD, BC, BD, CD → 총 6가지.

---

📌 2. 조합을 구현하는 2가지 방식

✅ (1) 재귀 + 백트래킹 방식​

#include <iostream>
#include <vector>
using namespace std;

int N = 4, K = 2;
vector<int> arr = {1, 2, 3, 4}; // 원소
vector<int> combination;

void comb(int start, int depth) {
//start : 이번 단계에서 선택할 수 있는 인덱스의 시작 위치 / 중복 없이 선택하도록 보장해줌
// depth : 현재까지 몇 개를 선택했는지 확인(카운트)
    if (depth == K) { // 기저 조건: K개를 모두 선택했을 때
        for (int num : combination) cout << num << " ";
        cout << '\n';
        return;
    }

    for (int i = start; i < N; i++) { //rksmdgks tjsxorwl ahen ghcnf
        combination.push_back(arr[i]);  // i번째 원소를 선택
        comb(i + 1, depth + 1);         
// 다음 선택 진행 (중복 X → i+1부터 시작) 다음 선택은 항상 현재보다 뒤의 원소만 보기(중복방지)
        combination.pop_back();         // 백트래킹: 선택했던 것을 되돌림
    }
}

int main() {
    comb(0, 0);
    return 0;
}

가장 많이 쓰는 조합 구현 방식.

comb(start, depth) : 현재 위치에서 시작해서 선택 개수를 관리.

백트래킹 으로 불필요한 가지치기를 쉽게 할 수 있음.

​

예를 들어 {1,2,3,4} 중 2개를 고르는 경우:

comb(0,0) → i=0 선택: {1}
  comb(1,1) → i=1 선택: {1,2} → 출력
  comb(1,1) → i=2 선택: {1,3} → 출력
  comb(1,1) → i=3 선택: {1,4} → 출력
comb(0,0) → i=1 선택: {2}
  comb(2,1) → i=2 선택: {2,3} → 출력
  comb(2,1) → i=3 선택: {2,4} → 출력
comb(0,0) → i=2 선택: {3}
  comb(3,1) → i=3 선택: {3,4} → 출력

​

🌿 이 방식의 장점

코드가 짧고 깔끔하다, 모든 조합을 중복 없이 생성할수 있다

백트래킹의 전형적 패턴이라 문제풀이에 응용이 쉽다

​

✅ (2) next_permutation 이용 (순열 기반 조합)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N = 4, K = 2;
    vector<int> arr = {1, 2, 3, 4};
    vector<int> bitmask(N - K, 0);  // 0이 앞에
    bitmask.insert(bitmask.end(), K, 1);  // 1이 뒤에

    do {
        for (int i = 0; i < N; i++) {
            if (bitmask[i]) cout << arr[i] << " ";
        }
        cout << '\n';
    } while (next_permutation(bitmask.begin(), bitmask.end()));
    
    return 0;
}

순열함수지만 조합을 쉽게 구할 수 있음.

bitmask에서 1이 선택된 위치가 조합이다.

대량의 조합을 순서 없이 구할 때 매우 깔끔함.

---

📌 3.활용 예시

조합은 다음 문제 유형에 자주 활용됩니다:

N개 중 K개 선택 (팀 구성, 부분집합, 메뉴 조합 등)

브루트포스 (완전탐색)

DFS 백트래킹 최적화 문제

BFS 상태 줄일 때

---

📌 4. 뽑을가 말까 결정하면서 진행하는 재귀함수

(백트레킹느낌! 매번 선택/비선택으로 나뉘는 이진트리형태)

#include <iostream>
#include <vector>

using namespace std;

void Combination(vector<char> arr, vector<char> comb, int r, int index, int depth){
/*arr : 전체 원소들 (예: {a, b, c, d, e})
comb : 현재까지 선택된 조합 결과 (선택된 원소들을 담음)
r : 앞으로 몇 개 더 뽑아야 하는지
index : comb 벡터의 어느 위치에 넣을 건지
depth : arr에서 몇 번째 원소를 보고 있는지*/
    if (r == 0)
    {
        for(int i = 0; i < comb.size(); i++) cout << comb[i] << " ";
        cout << endl;
    }
    else if (depth == arr.size()) return;
// depth == n // 계속 안뽑다가 r 개를 채우지 못한 경우는 이 곳에 걸려야 한다.
  
    else
    {
        // arr[depth] 를 뽑은 경우
        comb[index] = arr[depth]; // 현재원소 뽑기
        Combination(arr, comb, r - 1, index + 1, depth + 1);
// 현재원소 뽑고 -> 남은개수 r-1 -> comb의 위치를 idx+1에 담음 -> 다음 depth로 진행
        
        // arr[depth] 를 뽑지 않은 경우
        Combination(arr, comb, r, index, depth + 1);
// 현재원소 안뽑고 -> r유지 -> idx그대로 -> 다음 depth로 진행
    }
}

int main()
{
    vector<char> vec = {'a', 'b', 'c', 'd', 'e'};  // n = 5
    
    int r = 3;
    vector<char> comb(r);
    
    Combination(vec, comb, r, 0, 0);  // {'a', 'b', 'c', 'd', 'e'}의 '5C3' 구하기 

    return 0;

- a 선택 → b 선택 → c 선택 → [출력]
               → d 선택 → [출력]
               → e 선택 → [출력]
- b 선택 → c 선택 → d 선택 → [출력]
               → e 선택 → [출력]
... 등등

이런 느낌임

"선택/비선택 패턴은 확장성이 좋음 (예: 부분집합, DFS 등)"

​

이게 무슨 말이냐!!!

"분기를 두 개로 구분한다" :

조합(Combination) 문제를 풀 때, 매 원소마다 "뽑을까?" 또는 "안 뽑을까?" 이렇게 2가지 선택지를 매번 가지게 됨

즉, 재귀가 매 원소마다 이렇게 분기하는거!

​

ex) 배열: { 1, 2, 3, 4 } k = 2개를 뽑기

처음 호출:	분기1: 1을 뽑는다	분기2: 1을 안 뽑는다
Combination (v, cbn, k=2, idx=0, depth=0)	cbn[0] = 1 k를 하나 줄이고 → k=1 depth 하나 증가 → depth=1	cbn 건드리지 않음 k는 그대로 2 depth 증가 → depth=1
현재 depth=0 → 원소: 1	Combination (v, cbn, k=1, idx=1, depth=1) 재귀호출	Combination (v, cbn, k=2, idx=0, depth=1) 재귀호출

이렇게 계속 진행

각 단계에서 "뽑을까" vs "안 뽑을까" 로 분기가 두 갈래로 나눠진다.

그래서 이걸 "이진 트리처럼 분기" 한다고도 설명함

cbn[idx] = v[depth];
Combination(v, cbn, k-1, idx+1, depth+1);  // 분기1: 뽑음

Combination(v, cbn, k, idx, depth+1);      // 분기2: 안 뽑음

요런식으로!!!

그림으로 표현하면 이렇게 내려가는 구조임

depth=0 (1 선택 여부)
├── 선택함 (1)
│   ├── 선택함 (2)
│   └── 선택 안 함 (3)
└── 선택 안 함 (1)
    ├── 선택함 (2)
    └── 선택 안 함 (3)

이걸 조금 더 확장해서

조합 중에서 합이 제일 큰 것을 찾아 반환하는 방식으로 변환해보면

​

예시코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void Combination(vector<int>& v, vector<int>& cbn, int k, int idx, int depth, int& maxSum) {
    if (k == 0) {
        int sum = 0;
        for (int i = 0; i < cbn.size(); ++i)
            sum += cbn[i];
        maxSum = max(maxSum, sum);
    }
    else if (depth == v.size()) {
        return;
    }
    else {
        // 선택하는 경우
        cbn[idx] = v[depth];
        Combination(v, cbn, k - 1, idx + 1, depth + 1, maxSum);

        // 선택하지 않는 경우
        Combination(v, cbn, k, idx, depth + 1, maxSum);
    }
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> vec(N);
    for (int i = 0; i < N; ++i)
        cin >> vec[i];
    
    vector<int> cbn(K);
    int maxSum = 0;
    
    Combination(vec, cbn, K, 0, 0, maxSum);
    
    cout << "최대 합: " << maxSum << endl;

    return 0;
}

void Combination (vector<pair<int,int>>&v, int cnt, int depth, int Cal, int sum_c, int sum_s, int& max_s){ ​ if(cnt==0){ max_s = max(sum_s, max_s); sum_c = 0; sum_s = 0; } ​ else if (depth == v.size()) return; //배열 다 돌았는데 뽑을게 남았을 때 ​ else { sum_s += v[depth].first; // 먹으면 더하기 sum_c += v[depth].second; Combination (v, cnt-1, depth+1, Cal, sum_c, sum_s, max); //먹음 Combination(v, cnt, depth+1, Cal, sum_c, sum_s, max); //안먹음 } }

void Combination (vector<pair<int,int>>&v, int cnt, int depth, int Cal, int sum_c, int sum_s, int& max_s){ ​ if(cnt==0){ if(sum_c <= Cal) // 칼로리 제한 조건 추가 max_s = max(sum_s, max_s); return; } ​ if (depth == v.size()) return; ​ // 현재 것을 선택하는 경우 Combination (v, cnt-1, depth+1, Cal, sum_c + v[depth].second, sum_s + v[depth].first, max_s); ​ // 현재 것을 선택하지 않는 경우 Combination(v, cnt, depth+1, Cal, sum_c, sum_s, max_s); }

이렇게 하면 재귀 호출 위에서 sum_s와 sum_c의 값을 직접 건드리기 때문에 이후의 다른 경로에서 sum_s, sum_c 값이 꼬일 수 있어. ​ 👉 그래서 일반적으로는 "매개변수로 넘겨준 값은 재귀 호출 안에서 변경만 한다" 라고 생각하면 안전함. ​ 3️⃣ 핵심 변화 요약 sum_s, sum_c는 계속 누적된 값을 넘겨주고 재귀 호출 후에 값을 복구할 필요 없음 → 깔끔 cnt==0일 때만 max_s 갱신 ​ 4️⃣ 왜 이렇게 하는가? 재귀는 "함수 호출 스택"을 사용하므로 sum_s, sum_c를 바꾸고 다시 돌려놓는 것보단 아예 인자로 넘기는 게 안정적이고 실수 확률도 줄어듬. ​ 실전 코딩테스트에서 "이렇게 매개변수 전달하는 방식" 을 많이 씀.

Combination(v, cnt-1, depth+1, Cal, sum_c + v[depth].second, sum_s + v[depth].first, max_s);

​

이렇게 호출을 했을 떄

이건

현재 단계의 sum_c, sum_s 값에는 영향이 없다.

대신, 재귀로 내려가는 다음 함수 호출에만 새로운 값이 넘어간다.

를 의미한다!!!!

​

예를 들어서

현재 sum_s = 10, sum_c = 30, v[depth] = {5, 20} 라고 해보자.

Combination(v, cnt-1, depth+1, Cal, 30+20, 10+5, max_s);

이 호출은 → sum_c = 50, sum_s = 15 를 다음 함수에게 넘겨줌

하지만 현재 함수의 sum_c, sum_s는 여전히 30, 10 상태.

​

✅ 왜 그럴까?

매개변수로 넘겨주는 건 → 새로운 복사본처럼 넘어감 (값 전달 call-by-value)

즉, 호출이 끝나고 돌아오면 원래 값 유지됨.

이게 바로 재귀가 가지치기(탐색)을 잘 할 수 있는 이유

​

✅ 만약 sum_c, sum_s를 전역 변수처럼 바꾸면?

그땐 정말로 계속 누적돼서 꼬이게 되므로😅

그래서 전역 상태 변경 대신 이렇게 "함수 인자로만 넘기는 패턴" 사용

​

++++++)

void Combination (vector<pair<int,int>>&v, int cnt, int depth, int Cal, int sum_c, int sum_s, int& max_s)

여기에서 max_s 에 참조자가 붙는 이유!!!

기본적으로 재귀호출의 특징

재귀함수는 계속 깊이 들어갔다가 다시 돌아오는데

함수 안에서 지역변수로 선언된 변수들은 호출이 끝나면 사라져.

그래서 maxSum을 그냥 int maxSum으로 쓰면 → 매번 새로 복사본 만들어서 재귀 호출할 때마다 독립적인 값으로 존재함.

​

✅ 우리가 원하는 동작은?

최대값을 전체 탐색 동안 계속 갱신하고 유지하는 것.

즉, 어떤 재귀호출에서 최대값이 갱신되면 → 그 값이 바깥(이전 호출, 전체 프로그램)에 반영되어야 함.

​

✅ 참조자 (&) 를 붙이

해당 함수 호출 안에서 maxSum 값을 변경하면, 이 값이 원본으로 바로 반영됨.

즉, 함수 호출마다 maxSum 변수가 공유됨.

​

✅ 만약 & 안 붙이면?

각 재귀호출마다 maxSum의 복사본이 만들어짐

각 호출에서 최댓값을 갱신해도, 바깥에서는 반영되지 않음 → 결과가 항상 0 나올 수도 있음.

​

void Combination(int sum, int maxSum) { maxSum = max(maxSum, sum); }	void Combination(int sum, int& maxSum) { maxSum = max(maxSum, sum); }
위처럼 int maxSum 이라면 → 호출이 끝나면 maxSum 갱신 안 됨.	이렇게 int& maxSum 이라면 → 호출 안에서 바뀐 값이 계속 유지됨.

조합 공부 끝!!!!

​

+ 부분집합 구하는 방법

나는 for문으로 함수를 계속 호출했는데 이러면 runtime errer뜸

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<int>& arr, int depth, vector<int>& path, int& totalCount) {
/*arr : 전체 원소들 (예: {1,2,3,4,5,6})
path: 지금까지 선택한 원소 (부분집합)
totalCount: 부분집합의 개수를 세는 변수
depth : arr에서 몇 번째 원소를 보고 있는지*/

    if (depth == arr.size()) { // 재귀 끝나는 종료 조건 : 전체 원소를 다 고려했을 때(=마지막까지 도달했을 때)
        if (!path.empty()) { //부분집합이 공집합이 아니면 (path.empty() → 원소가 하나라도 있으면) cnt 증가 + 출력
            totalCount++;
            for (int num : path) cout << num << " ";
            cout << endl;
        }
        return;
    }

    // 포함하는 경우
    path.push_back(arr[depth]);
    dfs(arr, depth + 1, path, totalCount);
    path.pop_back();
    // 현재 원소 arr[depth] 를 선택함 (path에 넣음) 다음 원소 (depth + 1)로 이동
    // 재귀가 끝나고 나면 path.pop_back() 으로 방금 선택한 원소를 되돌림 (백트래킹)
    // 이렇게 안 되돌리면 path가 계속 길어짐 → "선택을 취소" 하는 단계

    // 포함하지 않는 경우 -> 다음으로 넘어감
    dfs(arr, depth + 1, path, totalCount);
}

int main() {
    int N = 6;
    vector<int> arr = {1, 2, 3, 4, 5, 6};
    vector<int> path;
    int totalCount = 0;

    dfs(arr, 0, path, totalCount);
    cout << "총 경우의 수: " << totalCount << endl;
    return 0;
}

dfs(0) → depth 0 → 원소 1을 포함하냐 마냐
|
├── 포함 (path={1})
|    └ dfs(1)
|        ├── 포함 (path={1,2})
|        |    └ dfs(2)
|        |        ├── 포함 (path={1,2,3}) → 출력
|        |        └── 미포함 (path={1,2}) → 출력
|        └── 미포함 (path={1})
|             └ dfs(2)
|                 ├── 포함 (path={1,3}) → 출력
|                 └── 미포함 (path={1}) → 출력
└── 미포함 (path={})
     └ dfs(1)
         ├── 포함 (path={2})
         └── 미포함 (path={})

이런 느낌으로