[1182] 부분수열의 합 - 백트랙킹 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

---

[ 문제 접근 ]

 

문제를 읽고 멱집합 ( powerSet ) 구하면 되겠거니 싶었지만,

항상 구현이 문제였다.

 

어렵진 않았지만 마지막에 모든 원소의 합이 0일때는 공집합의 0 도 있기 때문에 -1을 해줘야함을  어렵게 생각 해냈다.

---

[ 최종 코드 ]

 

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
 
using std::cin; using std::cout;
using std::vector;

int s, n;
int sum;
int cnt;
int cnt_false = 0;
vector<int> vec;
bool include[21];


void powerSet(int k) {
	
	if (k==n) {
		sum = 0;
		for (int i = 0; i < n; i++) {
			if (include[i]) {
				sum += vec[i];
			}
		}
		if (sum == s)  cnt++;
		return;

	}
	
	include[k] = false;
	powerSet(k + 1);

	include[k] = true;
	powerSet(k + 1);
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> s;
	int temp = n;
	while (temp--) {
		int a;
		cin >> a;
		vec.push_back(a);
	}
	powerSet(0);
	if (s == 0)cnt--;
	cout << cnt;

	return 0;
}

---

[ 다른 사람 풀이 ]

#include<iostream>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Dest, Answer;
int Arr[MAX];
 
void Input()
{
    cin >> N >> Dest;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
}
 
void DFS(int Idx, int Sum, int Size)
{
    if (Idx == N)
    {
        if (Sum == Dest && Size != 0)
        {
            Answer++;
        }
        return;
    }
 
    DFS(Idx + 1, Sum + Arr[Idx], Size + 1);
    DFS(Idx + 1, Sum, Size);
}    
 
void Solution()
{
    DFS(0, 0, 0);
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

---

[ Key Point ]

 

- 다른 사람 풀이를 보니 재귀함수에 size 인수로 아무것도 없는 공집합일 경우 cnt++ 가 안되게 할 수 있다는 점을 새로 알았다.

---

[ 다른 사람 풀이 ]

 

ref :: https://yabmoons.tistory.com/182