[Computer Algorithms] Combination (조합)

N개 들어있는 배열에서 i개 고르는 경우를 모두 출력하는 알고리즘이다. mask를 이용해서 true인 자리에 있는 것을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    for (int i = 1; i <= N; i++)
    {
        cout << i << "개 선택하는 경우:\n";
        vector<bool> mask(arr.size(), false);
        fill(mask.begin(), mask.begin() + i, true); // 앞의 i개를 true로 설정
        do
        {
            for (int j = 0; j < arr.size(); j++)
            {
                if (mask[j])
                    cout << arr[j] << " ";
            }
            cout << endl;
        } while (prev_permutation(mask.begin(), mask.end())); // 이전 조합을 찾음
        cout << endl;
    }

    return 0;
}

 

10000의 이전 조합: 01000

01000의 이전 조합: 00100

00100의 이전 조합: 00010

00010의 이전 조합: 00001

00001의 이전 조합: while 탈출

 

11000의 이전 조합: 10100

10100의 이전 조합: 10010

10010의 이전 조합: 10001

10001의 이전 조합: 01100

...

00011의 이전 조합: while 탈출

 

1개 선택하는 경우:
1 
2 
3 
4 
5 

2개 선택하는 경우:
1 2 
1 3 
1 4 
1 5 
2 3 
2 4 
2 5 
3 4 
3 5 
4 5 

3개 선택하는 경우:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

4개 선택하는 경우:
1 2 3 4 
1 2 3 5 
1 2 4 5 
1 3 4 5 
2 3 4 5 

5개 선택하는 경우:
1 2 3 4 5