[백준 1182번] 부분수열의 합 (C/C++)

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

1182번: 부분수열의 합

---

부분 수열을 선택하기 위해서 길이가 1 ~ n까지의 부분 수열을 모두 뽑았습니다.

하지만, n의 최대 값이 20이기 때문에 순서가 다른 수열까지 모두 뽑을 경우 시간초과가 발생합니다.

 

아래 풀이의 핵심은 17번째 라인입니다. i의 초기값이 r로 시작하고, 재귀 함수 호출 시 i + 1을 전달함으로써 다음 선택할 숫자를 이전에 선택한 숫자 다음 인덱스부터 확인함으로써 순서만 다른 수열은 계산에서 제외됩니다.

#include <bits/stdc++.h>
using namespace std;

int arr[21];    // 전체 수열을 저장하는 배열
bool isused[21];    // 숫자의 선택 여부를 저장하는 상태 배얄
int selected[21];   // 선택된 숫자를 저장하는 배열

int n, s, ans = 0;

void seq(int r, int m, int a){  // 길이가 a인 수열을 선택할 때, 
                                // index r 이상의 범위에서 a-m+1개의 숫자를 선택하는 함수
    if(m == a + 1){ // 수열의 길이만큼 숫자를 선택한 경우
        int sum = 0;
        for(int i = 0; i < a; i++) sum += selected[i];  // 선택된 숫자들을 모두 합함.

        if(sum == s) ans++; // 선택된 숫자들의 합이 s인 경우, 경우의 수 증가
    }else{
        for(int i = r; i < n; i++){
            if(!isused[i]){
                isused[i] = true; selected[m - 1] = arr[i];
                seq(i + 1, m + 1, a);
                isused[i] = false;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> s;

    for(int i = 0; i < n; i++)  cin >> arr[i];
    
    for(int i = 1; i <= n; i++) seq(0, 1, i); // 부분수열의 길이가 1 ~ n이 되도록 함
    cout << ans;
}

아래는 사용한 테스트 케이스입니다.

5 3
3 2 3 2 5

20 5
3 2 3 2 5 6 1 2 4 5 1 2 5 6 8 2 3 5 5 1