백준 부분수열의합 1182

1. 백준 부분수열의합 1182

2. 컴퓨팅적 스킬

• 재귀호출 사용, 조합 사용

3. 컴퓨팅적 사고

• next_permutation을 사용한 조합을 이용한 풀이 방법 1
  순열과 조합중 조합을 사용하여 각각의 부분집합의 경우를 모두 구해준다. 하나씩 check변수에 모든 값을 true로 바꾸어준 후, 맨 앞에 있는 값들을 false로 바꾸면서 모든 부분집합의 경우를 구해준다.

• 재귀함수 백트래킹을 이용한 풀이 방법 2

1. m == 0 일때 공집합을 빼주어야한다. 양수라고 하였음. 정수에서 양수의 크기만 가지므로 공집합은 제외해야함
2. int cnt = 0;의 값이 계속초기화된다고 할 수 있지만, 결과값 반환할때는 그값이 더해진값만 반환된다.
3. 경우의 수 의 문제임 따라서, 그값이 1로반환되어 한번의 경우의수 0번의 경우의수를 반환하여 더해가다보면 최종 경우의 수를 반환하게 된다.
4. 정답일 경우는 sum == m이 같고, cnt ==값이 5개일때만 가능하다.
5. 비정답일 경우는 sum == m이 아닌경우에 cnt==값이 5개 일경우는 불가능하다.
   예를 들면, 도달했지만 값이 다를 수 있음 반례임

4. 풀이

재귀 백트래킹 풀이 1

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> ans;
int check[21];
int cnt = 0;
void dfs(vector<int> v,int n,int m, int idx, int sum){
    
    if(ans.size() > 0){
        
        int s = 0;
        for(int i=0; i<ans.size(); i++){
            s += ans[i];
        }
        if(s == m){
            cnt +=1;
        }
    }
    
    for(int i=idx; i<n; i++){
        if(check[i]){
            continue;
        }
        check[i] = true;
        ans.push_back(v[i]);
        dfs(v,n,m,i,sum);
        check[i] = false;
        ans.pop_back();
    }
}

int main(void){
    int n,m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    dfs(v,n,m,0,0);
    cout << cnt;
    return 0;
}

재귀 백트래킹 풀이 2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int ans = 0;
void dfs(vector<int> v, int m, int cnt,int sum){
    
    // 합이 m과 같을 경우
    if(cnt == v.size()){
        if(sum == m){
            ans +=1;
        }
        return;
    }
    else if(cnt == v.size()){
        return;
    }
    dfs(v,m,cnt+1,sum+v[cnt]);
    dfs(v,m,cnt+1,sum);
}

int main(void){
    int n,m;
    cin >> n >> m;
    vector<int> v(n);
    
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    //공집합 빼주기
    if(m==0){
        ans -=1;
    }
    dfs(v,m,0,0);
    cout << ans << '\n';

    return 0;
}

next_permutation 조합 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int n,m;
    cin >> n >> m;
    vector<int> v(n);
    bool check[21];
    for(int i=0; i<n; i++){
        cin >> v[i];
    }
    
    int cnt = 0;
    for(int i=0; i<20; i++){
        check[i] = true;
    }
    
    for(int i=0; i<n; i++){
        check[i] = false;
        do{
            int sum = 0;
            for(int j=0; j<n; j++){
                if(check[j] != true){
                    sum += v[j];
                }
            }
            if(sum == m){
                cnt +=1;
            }
            
        }while(next_permutation(check,check+n));
    }
    cout << cnt;
    
    return 0;
}