전체 탐색에서 부분합 문제를 비트를 사용하는 방법

부분합 문제

 

예를들어,

vec{1,2,4,5,11} 이라는 숫자의 부분합으로 10이 나올 수 있는지 파악하는 방법으로 비트연산으로 하는 방법이 있어서 블로그에 기록해본다

 

비트연산을 활용하여 하는 방법이 있는데,

위의 벡터의 부분합의 가지수는 총 32가지 즉, 비트로 11111 (2^5) 로 나타낼 수 있다.

예를 들면 1, 4, 5를 선택 하면 10이 나오는데, 이는 비트로 01101(오른쪽부터 vec[0]이라고 치면) 로 나타낼 수 있다.

 

코드로 치면 다음과 같다

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	bool isCanmake = false;

	vector<int> vec = { 1,2,4,5,11 };

	int answer = 10;

	for (int i = 0; i < (1 << vec.size()); ++i) // 32가지 for문을 돌리는 구간
	{
		int sum = 0;

		for (int j = 0; j < vec.size(); ++j) // 5개 숫자를 찾는 구간
		{
			if (i & 1 << j)
			{
				sum += vec[j];
			}
		}
		if (sum == answer)
		{
			isCanmake = true;
			break;
		}
	}

	if (isCanmake)
	{
		cout << "True";
	}
	else
	{
		cout << "False";
	}

	return 0;
}