모든 부분 집합 구하기

 

{a, b, c, d} 의 집합이 있을 때 만들 수 있는 모든 부분집합의 수를 구해보았다 (단 공집합은 제외)

원소가 있다, 없다 로 나뉘기 때문에 포함하는 경우와 포함하지 않는 경우를 생각하면서 작성

 

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

string str = "abcd";
vector<vector<char>> res;

void pick(int n, vector<char>& picked, int toPick, int pos)
{
    if (toPick == 0)
    {
        res.push_back(picked);
        
        int size = picked.size();
        for(auto tmp : picked) {
            cout << tmp << " ";
        }
        cout << endl;


        return;
    }

    for (int next = pos; next < n; next++)
    {
        //picked라는 배열의 끝에 next라는 변수를 추가한다.
        picked.push_back(str.at(pos));
        //이 과정을 toPick-1을 한 채로 다시 실행한다.
        pick(n, picked, toPick - 1, ++pos);
        //picked란 배열중 가장 마지막 배열의 원소를 제거한다.
        picked.pop_back();

        // pick(n, picked, toPick, pos); //중복. 현재의 함수와 같은 기능을 하므로. - 전부 같은 파라미터
    }
}

int main()
{
    int n = str.size();
    vector<char> v;
    
    for(int i = 1; i <= n; i++)
        pick(n, v, i, 0);

    cout << "*** "  << res.size();

    return 0;
}