백준 1182 부분수열의 합 Python

🔷 부분수열의 합

📌 문제

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

📌 입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다.
(1 ≤ N ≤ 20, |S| ≤ 1,000,000)

둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.
주어지는 정수의 절댓값은 100,000을 넘지 않는다.

📌 출력

합이 S가 되는 부분수열의 개수를 출력한다.

📌 예제 입력 1

5 0
-7 -3 -2 5 8

📌 예제 출력 1

1

📌 예제 입력 2

3 3
1 2 3

📌 예제 출력 2

2

📌 문제 설명

우리가 풀어야 하는 문제는 단순하지만 실수하기 쉽습니다.
수열의 각 원소를 하나 이상 선택해 부분수열을 만든 뒤, 그 합이 정확히 S가 되는 경우를 세야 합니다.
여기서 중요한 건 반드시 하나 이상의 숫자를 선택해야 하고, 아무 것도 선택하지 않는 공집합은 제외해야 한다는 점입니다.

📌 예시를 하나하나 살펴보기

🔷 예제 입력 1 다시 보기

5 0
-7 -3 -2 5 8

수열: [-7, -3, -2, 5, 8], 목표 합: 0
모든 경우를 살펴보면 합이 0이 되는 경우는 [-3, -2, 5] 하나뿐입니다.
따라서 출력은 1입니다.

🔷 예제 입력 2 살펴보기

3 3
1 2 3

수열: [1, 2, 3], 목표 합: 3입니다.
이번에도 모든 부분수열을 하나하나 따져봅니다.

📌 가능한 부분수열

• [3] → 합: 3
• [1, 2] → 합: 1 + 2 = 3

이 두 가지가 목표 합 3이 됩니다.
다른 조합들은 모두 3이 아닙니다.

📌 다른 경우는 왜 안 되나?

• [1] → 합: 1 (3이 아님)
• [2] → 합: 2 (3이 아님)
• [1, 3] → 합: 4 (3이 아님)
• [2, 3] → 합: 5 (3이 아님)
• [1, 2, 3] → 합: 6 (3이 아님)

이처럼 하나하나 확인해보면 목표 합 3이 되는 경우는 [3]과 [1, 2], 총 두 가지입니다.

📌 최종 출력

그래서 예제 2의 답은 2입니다.

📌 아이디어

이 문제를 풀기 위한 핵심 아이디어는, 각 원소마다 선택하거나 선택하지 않는 두 가지 경우를 모두 탐색하는 것입니다.
이 선택/비선택을 재귀적으로 구현하여 모든 경우를 빠짐없이 확인하고, 공집합을 제외한 합이 S인 경우를 카운트합니다.
아이디어를 단계별로 정리하면 다음과 같습니다.

🔢 1️⃣ 각 원소마다 선택하거나 선택하지 않는다

수열의 각 원소는 두 가지 선택지를 가집니다.

• 현재 원소를 선택한다
• 현재 원소를 선택하지 않는다

이 선택을 모든 원소에 대해 반복하면 모든 가능한 부분수열을 만들 수 있습니다.
이 선택과 비선택은 비트 패턴으로 표현할 수 있습니다.
예를 들어 수열이 [1, 2, 3, 4]라면, 선택/비선택의 결과는 다음과 같이 나타낼 수 있습니다.

선택 상태(비트)	선택된 원소	합
0001	[4]	4
0101	[2, 4]	6
1001	[1, 4]	5
1111	[1, 2, 3, 4]	10

각 자리(비트)가 1이면 해당 원소를 선택한 것이고, 0이면 선택하지 않은 것입니다.
각각의 조합을 계산해 합이 S와 같은지를 확인하면 됩니다.

🔢 2️⃣ 이렇게 해서 \(2^N\)개의 경우가 나온다

앞에서 보았듯이, 각 원소마다 선택/비선택 두 가지 선택지가 있기 때문에, \(N\)개의 원소에 대해서는 총 \(2^N\)개의 경우가 만들어집니다.
왜냐하면 \(2 × 2 × 2 × … = 2^N\)이 되기 때문입니다.

경우의 수 표

원소 개수 \(N\)	경우의 수 \(2^N\)
1	2
2	4
3	8
…	…
20	1,048,576

이렇게 \(2^N\)개의 모든 경우를 탐색해야 하므로 시간복잡도는 \(O(2^N)\)입니다.
하지만 \(N ≤ 20\)이기 때문에 이 방법이 가능합니다.

🔢 3️⃣ DFS로 재귀적으로 구현한다 (트리 시각화)

앞에서 설명한 선택/비선택을 코드로 구현할 때는 DFS(깊이 우선 탐색)이 적합합니다.
DFS를 사용하면 현재 단계에서 두 가지 갈래를 만들어 재귀적으로 탐색할 수 있습니다:

• 왼쪽 가지: 현재 원소를 선택하지 않는다
• 오른쪽 가지: 현재 원소를 선택한다

트리 시각화 예시

                         시작 (합=0, 비트=0000)
                           /                     \
                선택X                          선택O (1)
         (합=0, 비트=0000)           (합=1, 비트=1000)
           /          \                      /            \
     선택X           선택O           선택X            선택O
 (합=0,비트=0000)  (합=2,비트=0010)   (합=1,비트=1000)   (합=3,비트=1010)

각 리프 노드 예시

• 왼쪽-왼쪽: 비트=0000, 선택된 원소: [], 합=0
• 왼쪽-오른쪽: 비트=0010, 선택된 원소: [2], 합=2
• 오른쪽-왼쪽: 비트=1000, 선택된 원소: [1], 합=1
• 오른쪽-오른쪽: 비트=1010, 선택된 원소: [1,2], 합=3

✅ 이렇게 DFS는 왼쪽/오른쪽으로 탐색하며 모든 리프 노드에 도달합니다.
각 리프에서 공집합 여부와 합이 S와 같은지를 확인하고, 조건을 만족하면 카운트를 올립니다.

---

🔷 전체 코드

N, S = map(int, input().split())
arr = list(map(int, input().split()))

cnt = 0

def SubSet(index, total, selected):
    global cnt

    if index == N:
        if total == S and selected > 0:
            cnt += 1
        return

    # 현재 원소를 선택하지 않음
    SubSet(index + 1, total, selected)

    # 현재 원소를 선택함
    SubSet(index + 1, total + arr[index], selected + 1)

SubSet(0, 0, 0)

print(cnt)

🔷 코드 설명

1️⃣ 종료조건

if index == N:
    if total == S and selected > 0:
        cnt += 1
    return

✅ 종료조건은 모든 원소를 탐색한 후, 리프 노드에 도달했을 때입니다.
이때 현재까지 선택한 부분수열이 유효한지 확인합니다:

• total == S : 현재까지 선택한 원소들의 합이 목표 합 S와 같은지
• selected > 0 : 선택한 원소가 하나 이상인지 (공집합 제외)

두 조건을 모두 만족하면 cnt++로 카운트를 하나 올립니다.
그 후 return으로 재귀를 종료합니다.

2️⃣ 왼쪽 노드 탐방 — 현재 원소를 선택하지 않음

SubSet(index + 1, total, selected)

✅ 왼쪽 노드는 현재 인덱스의 원소를 선택하지 않고 다음으로 진행하는 경우입니다.
비트 패턴에는 0을 추가하며, 선택하지 않았음을 표현합니다.
total과 selected는 변하지 않습니다.

예시 (수열: [1,2,3], 목표 합: S)

인덱스	비트 패턴	선택된 원소	합	selected
0	[]	[]	0	0
1	[0]	[]	0	0
2	[00]	[]	0	0
3	[000]	[]	0	0

🌱 왼쪽 가지로만 진행하면 인덱스가 하나씩 늘어날 때마다 비트패턴에 0이 붙고, 공집합 상태가 유지됩니다.

3️⃣ 오른쪽 노드 탐방 — 현재 원소를 선택함

SubSet(index + 1, total + arr[index], selected + 1)

✅ 오른쪽 노드는 현재 인덱스의 원소를 선택하고 다음으로 진행하는 경우입니다.
비트 패턴에는 1을 추가하며, 선택했음을 표현합니다.
total에는 현재 원소의 값을 더하고, selected를 1 증가시킵니다.

예시 (수열: [1,2,3], 목표 합: S)

인덱스	비트 패턴	선택된 원소	합	selected
0	[]	[]	0	0
1	[1]	[1]	1	1
2	[11]	[1,2]	3	2
3	[111]	[1,2,3]	6	3

🌱 오른쪽 가지로만 진행하면 인덱스가 하나씩 늘어날 때마다 비트패턴에 1이 붙고, 합과 선택한 개수가 증가합니다.

✅ 요약

• 왼쪽: [0] → [00] → [000] (선택X, total=0, selected=0)
• 오른쪽: [1] → [11] → [111] (선택O, total과 selected가 누적)

이처럼 인덱스별로 비트 패턴이 확장되고, 선택/비선택에 따라 합과 선택 개수가 달라집니다.
코드를 볼 때 트리 탐색을 이렇게 단계적으로 이해하면 됩니다.

🔷 결론

• 부분수열의 모든 경우를 탐색하기 위해 각 원소마다 선택과 비선택을 결정하며 DFS로 탐색한다.
• 왼쪽 가지는 현재 원소를 선택하지 않는 경로이며, 비트 패턴에 0을 추가한다.
• 오른쪽 가지는 현재 원소를 선택하는 경로이며, 비트 패턴에 1을 추가하고 합과 선택 개수를 누적한다.
• 리프 노드에 도달했을 때 공집합을 제외하고 합이 S와 같으면 카운트한다.