[C++] 부분집합 경우의 수 구하기

전체집합의 원소를 입력하면

원소의 개수가 3개인 부분집합들을 출력해 준다.

1. 전체집합의 원소개수입력

2. 전체집합의 원소 입력

3. 부분집합이 생기는 경우의 수 계산(확률의 조합 이용)

4. 전체집합의 앞에서부터 차례대로 3개씩 넣음

ex) 전체집합이 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 이라 하면

{1, 2, 3} {1, 2, 4} {1, 2, 5} ...{1, 2, 10}

{1, 3, 4} {1, 3, 5} ...          {1, 3, 10}

이런식으로 첫번째 고정한 후 나머지 차례대로 집어넣는다.

#include <iostream>
 
using namespace std;
 
int cnt = 0;
 
int GetCombination(int n, int r)
{
    // nCr = n-1Cr-1 + n-1Cr
    if (r == 0 || n == r)
        return 1;
    return (GetCombination(n - 1, r - 1) + GetCombination(n - 1, r));
}
 
 
void intputSubArr(int** arr, int e1, int e2, int e3)
{
    arr[cnt][0] = e1;
    arr[cnt][1] = e2;
    arr[cnt][2] = e3;
 
    cnt++;
}
 
int main()
{
    int n; //전체 집합의 갯수
 
    cout << "n: ";
 
    cin >> n;
 
    int e1, e2, e3; //부분집합의 원소 3개
    int combi = GetCombination(n, 3); // 부분집합의 개수
 
    int **arr = NULL;
    arr = new int*[combi];
    for (int i = 0; i < combi; i++)
    {
        arr[i] = new int[3];
    }    
    
    int *set = new int[n]; // 집합원소 갯수만큼 배열선언
 
    for (int i = 0; i < n; i++)
    {
        cout << i+1 << " element enter: ";
        cin >> set[i];
    }
 
    for (int i = 0; i < n-2; i++)
    {
        //앞에 두개(e1,e2), 한개(e3) 뽑음
        e1 = set[i];
        for (int t = i + 1; t < n - 1; t++)
        {
            e2 = set[t];
 
            for (int j = t+1; j < n; j++)
            {
                e3 = set[j];
                intputSubArr(arr, e1, e2, e3); //부분집합에 집어넣음
            }
 
        }
    }
 
    //print 
 
    for (int i = 0; i < combi; i++)
    {
        cout << "{ ";
        for (int j = 0; j < 3; j++)
        {
            cout << arr[i][j] << " ";
        }
        cout << " }"<<endl;
    }
 
}