[DFS] 1182번 부분집합의 합

1182번 부분집합의 합

 

https://www.acmicpc.net/problem/1182

 

문제

N개의 정수로 이루어진 집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중에서 그 집합의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1≤N≤20, |S|≤1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 같은 수가 여러 번 주어질 수도 있다.

 

출력

첫째 줄에 합이 S가 되는 부분집합의 개수를 출력한다.

 

예제 입력

5 0
-7 -3 -2 5 8

 

예제 출력

1

 

해결방법

• 수열 중 n개를 선택 → DFS + 백트래킹
• 수열 중 연속된 수 선택 → Left & Right 탐색
• 수열 중 전체 경우 선택 → ???

 

 

⭐️ 1차 시도 ⭐️

틀렸습니다

 

void dfs(int ind){
    // 답을 찾은 경우
    if(sum.size()>0 && getSum()==m){
        ans++;
        return;
    }
    
    // DFS 탐색
    for(int i=ind; i<n; i++){
        if(!visited[i]){
            visited[i] = true;
            sum.push_back(arr[i]);
            dfs(i);
            sum.pop_back();
            visited[i] = false;
        }
    }
}

처음에 작성한 코드이다

집합에 대해 합을 만들 수 있는 부분 집합을 모두 탐색하였다

하지만 저 return 이 문제였다!!!

 

 

⭐️ 2차 시도 ⭐️

맞았습니다!!

 

만약 1 2 3 0 의 집합이 있고 m=6 이라고 가정해보자

1 2 3 에서 합이 m과 같기 때문에 ans++ 가 수행된다

하지만 return 때문에 다음 부분 집합은 1 2 0 으로 넘어간다

모든 경우를 해봐야 하기 때문에 return 은 빼줘야한다

 

 

✅ return 을 해야하는 경우는???

만약 DFS + 백트래킹 문제에서 전체 4개 중 3개를 뽑는 경우가 있다고 해보자

1 2 3 은 cnt=3 이기 때문에 옳은 순열이다

하지만 그 다음 순열은 1 2 3 4 이다. 이는 옳은 순열이 아니다

따라서 return 을 해주면 1 2 3 다음의 순열은 1 2 4 가 될 것 이다

하지만 이 문제에서는 cnt 의 개수가 따로 지정되지 않았다

따라서 모든 자리수의 부분 순열을 검사해야 하므로 return 을 하면 안된다 !!!

 

 

⭐️ 3차 시도 ⭐️

맞았습니다!!

 

기존에 해왔던 백트래킹 방법이 아닌 다른 방법으로 시도해봤다

아직 익숙하지 않은 방법이지만 다시 풀어보면서 연습해야겠다

void dfs(int ind,int sum,int len){
    // 노드의 끝에 도달함
    if(ind == n){
        // 공집합이 아니고, 집합의 합이 m과 일치할 때
        if(len > 0 && sum == m){
            ans++;
        }
        return;
    }
    
    // ind 인덱스 노드를 포함하는 경우
    dfs(ind+1,sum+arr[ind],len+1);
    // ind 인덱스 노드를 포함하지 않는 경우
    dfs(ind+1,sum,len);
}

 

 

소스코드

# Solution1

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;

int n,m,ans;
int arr[MAX];
bool visited[MAX];

vector<int> sum;

int getSum(){
    int res = 0;
    for(int i=0; i<sum.size(); i++){
        res += sum[i];
    }
    return res;
}

void dfs(int ind){
    // 답을 찾은 경우
    if(sum.size()>0 && getSum()==m){
        ans++;
    }
    
    // DFS 탐색
    for(int i=ind; i<n; i++){
        if(!visited[i]){
            visited[i] = true;
            sum.push_back(arr[i]);
            dfs(i);
            sum.pop_back();
            visited[i] = false;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    ans = 0;
    memset(visited, false, sizeof(visited));
    dfs(0);
    cout << ans << "\n";
}

# Solution2

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 21
#define INF 987654321
using namespace std;

int n,m,ans;
int arr[MAX];

void dfs(int ind,int sum,int len){
    // 노드의 끝에 도달함
    if(ind == n){
        // 공집합이 아니고, 집합의 합이 m과 일치할 때
        if(len > 0 && sum == m){
            ans++;
        }
        return;
    }
    
    // ind 인덱스 노드를 포함하는 경우
    dfs(ind+1,sum+arr[ind],len+1);
    // ind 인덱스 노드를 포함하지 않는 경우
    dfs(ind+1,sum,len);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    ans = 0;
    dfs(0,0,0);
    cout << ans << "\n";
}