알고리즘[C++]- Backtracking을 이용한 부분집합의 합(subset_sum)순서쌍 구하기.

문제

n개의 원소를 가진 정수의 집합 S가 주어지고,
임의의 정수 W가 주어졌을 때,
합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오.

---

입력

첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다.
둘째 줄에 n개의 정수가 주어진다.

---

출력

첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다.
둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다.
단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로)

---

 

※처음 문제를 보고 떠오른 생각

1. 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다.
2. Backtracking을 이용해서 모든 경우의 수를 구한다.
3. 유망성검사를 통해서 가지치기를 함.
4. 만약 뽑은 원소들의 합이 W면 종료.

 

ex) 만약 원소의 개수가 4개이고, W가 13이고 집합 S의 원소가 {3,4,5,6} 일 때 S의 원소들로 13을 만들 수 있는 경우의 수는 {3,4,6} 일 것이다. (3+4+6=13)

 

설계

1. 집합 S의 원소들로 13을 만들 수 있을지 없을지부터 따져봐야 할 것이다.  (S의 모든 원소들의 합이 W보다 크거나 같아야 한다.)  ->만들 수 없으면 0을 출력하면 된다.
2. 각각의 원소들을 더하는 경우와 안 더하는 경우 2가지가 있다. 그걸 코드상으로 include라는 배열을 만들어서 0이면 원소를 안 더했다는 뜻이고 1이면  원소를 더했다는 뜻이다.
3. 모든 경우의 수를 방문하는 것을 원칙으로 하지만 효율적으로 방문하기 위해서 유망성 검사를 한다.(코드 상으로는 promising함수이다.)
   • 유망성 검사 조건 1)
     1. 이때까지 더한 값과 다음 더하려는 값의 합이 W값을 초과하면 안 된다. (다음 값을 더할 때 W를 넘으니 굳이 탐색 안 해도 됨.)
   • 유망성 검사 조건 2)
     1. 이때까지 더한 값과 남아 있는 원소의 합(total)이 W보다 작으면 안 된다.(남아있는걸 다 더해도 W가 되지 않으니까 굳이 탐색할 필요가 없음.)
4.  유망성 검사를 해서 조건에 부합하면 가지치기를 하고 통과되면 탐색을 실시해서 결과를 구현함.

구현

1. 유망성 검사(pruning)

bool promising(int i, int weight, int total) {
	return (weight + total >= W) && (weight == W || weight + sub[i + 1] <= W);
} //유망성 검사를 해서 통과하면 1 리턴 안되면 0리턴 해서 가지치기 실시.

 

 

2. 부분집합을 더하는 함수

• weight는 현재 내가 더한 값의 합이고 total은 집합 S의 원소합이다.
• include [i+1]=true는 i+1번째 수를 내가 더해줬다는 뜻이고 false는 더하지 않았다는 뜻이다.
• 더했으면 weight의 값을 더해주고, 원소를 검사했으니 total값에서 그 원소의 값을 빼준다.
• 더하지 않았으면 weight의 값을 더해줄 필요가 없고, 원소를 검사했으니 total값에서 그 원소의 값을 빼준다.
• 종료 조건은 내가 더해준 값의 합이 W가 되면 종료한다.

void subset(int i, int weight, int total) {
	if (promising(i, weight, total)) {
		if (weight == W)
		{
			cnt++;
			string ab = "";
			for (int j = 1; j <= i; j++)
			{
				if (include[j] == 1)
					str.push_back(to_string(sub[j]));
			}
			str.push_back("");
			//ab에 저장된걸 스트링 배열에 넣고싶음
		}
		else
		{
			include[i + 1] = true;
			subset(i + 1, weight + sub[i + 1], total - sub[i + 1]);
			include[i + 1] = false;
			subset(i + 1, weight, total - sub[i + 1]);
		}
	}
}

---

가지치기의 조건만 잘 설정하면 쉽게 풀 수 있는 문제이다.

include배열을 굳이 써야 했나 싶지만, 문제에서 요구하는 출력을 하기 위해서는 어쩔 수 없는 선택인 것 같다..