백준 1182번 [부분수열의 합](C++) -yes6686- 티스토리

백준 문제 풀이: 1182 [부분수열의 합]

---

문제 링크: https://www.acmicpc.net/problem/1182

문제 설명:

N개의 정수로 이루어진 배열에서 부분수열의 합이 S가 되는 경우의 수를 구하는 문제입니다. 빈 부분수열은 포함되지 않습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[21]; // 입력된 배열
int n, s;    // 배열의 크기와 목표 합
int ans = 0; // 부분수열의 합이 S가 되는 경우의 수

// 부분수열을 탐색하는 재귀 함수
void solve(int depth, int sum) {
    if (depth == n) { // 배열의 끝까지 탐색한 경우
        if (sum == s) ans++; // 현재 합이 S와 같으면 정답 증가
        return;
    }

    // 현재 원소를 포함하지 않는 경우
    solve(depth + 1, sum);

    // 현재 원소를 포함하는 경우
    solve(depth + 1, sum + arr[depth]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s;

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

    // 부분수열 탐색
    solve(0, 0);

    // 결과 출력
    if (s == 0) ans--; // 공집합 제외
    cout << ans << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 백트래킹을 사용하여 모든 부분수열의 합을 탐색합니다. 현재 원소를 포함하거나 포함하지 않는 두 가지 경우를 재귀적으로 탐색합니다.
• 구현 세부사항:
  • solve(depth, sum): 현재 인덱스 depth와 부분수열의 합 sum을 기반으로 부분수열을 탐색
  • 종료 조건: depth == n일 때 sum == s인지 확인
  • 공집합을 제외하기 위해 s == 0인 경우 결과에서 1을 뺌
• 시간 복잡도 분석: O(2ⁿ)
  • N개의 원소에 대해 각 원소를 포함하거나 포함하지 않는 경우의 수

---

결과

주어진 배열에서 부분수열의 합이 S가 되는 경우의 수를 정확히 계산합니다. 모든 경우를 백트래킹으로 탐색하여 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!