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

문제

1182번: 부분수열의 합

---

문제 요약

N개의 정수로 된 수열에서 부분 수열을 뽑아낸 뒤,

부분 수열의 원소를 모두 더한 값이 입력값과 같은 경우의 수를 구하는 문제

---

문제 풀이

algorithm 헤더에 있는 prev_permutation() 함수를 사용했다.

이 함수를 사용한 이유는 다음과 같다.

1. 중복 없이 N개의 정수로 된 수열을 조합하기 위해서
2. 부분 수열의 원소 개수를 (1 ~ N)개까지 두고 조합하기 위해

먼저 N개의 정수로 된 수열을 벡터에 입력받는다.

그리고 N만큼 크기를 갖는 bool 타입 벡터를 만들고 0번째 인덱스부터 1씩 증가시키며 true로 초기화한다.

bool 타입 벡터의 원소가 true라면 N개의 수열에서 값을 가져와 sum 변수에 더해간다.

(이렇게 만들면 bool 타입 벡터 std가 0번째 인덱스만 true일 때, 부분 수열의 크기는 1이 된다. 또 0번째와 1번째 인덱스가 true일 때는 부분 수열의 크기는 2가 된다. 마지막에 0부터 N-1번째 인덱스가 모두 true일 때 부분 수열의 크기는 N개이다.)

만약 sum의 값과 입력값이 같으면 cnt를 1씩 증가 시켜주고, 최종적으로 cnt를 출력한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    int sum = 0, cnt = 0;

    vector <int> perm(n);
    for (int i = 0; i < n; i++) {
        cin >> perm[i];
    }

    vector <bool> std(n);
    for (int i = 0; i < n; i++) {
        std[i] = true;

        do {
            sum = 0;

            for (int r = 0; r < n; r++) {
                if (std[r] == true) {
                    sum += perm[r];
                }
            }

            if (sum == m) cnt++;
        } while (prev_permutation(std.begin(), std.end()));
    }

    cout << cnt;

    return 0;
}