백준 1182번: 부분수열의 합 (Python)

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

1182번: 부분수열의 합

---

Level: Silver II

Solved By: Backtracking

 

Backtracking을 통해서 풀 수 있는 문제였습니다. 부분 집합을 구하는 과정은 Recursive call을 통해 지금 현재 index에 해당하는 수를 부분집합에 포함시킬 것이냐 배제시킬 것이냐를 나누어서 코드를 쓸 수 있다면, 구현이 가능합니다.

즉, 하나의 수에 대해 2가지 경우를 고려하고, 연속적으로 N번 일어나기 때문에 Time Complexity는 O(2^N)이 됩니다.

그리고, 문제에서는 부분집합의 크기가 양수인 것으로만 합을 구하라 하였기 때문에 공집합이 구해질 경우, 제외할 수 있어야 합니다.

그래서 지금 현재 수가 몇 개가 포함되어 있는지 알 수 있는 배열을 선언하여, 이 또한 Recursive Call에 넣어주었습니다.

import sys
input = sys.stdin.readline

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

li = list(map(int, input().split()))
temp = []

res = 0

def backTracking(index, sum_value, t):
    # print(index, sum_value)
    if index == len(li):
        if sum_value == S and len(t) != 0:
            # print(t)
            global res
            res += 1
        return
    
    # 해당 index의 수를 부분 수열의 수로 채택하는 경우
    t.append(li[index])
    backTracking(index+1, sum_value + li[index], t)
    t.pop()
    # 아닌 경우
    backTracking(index+1, sum_value, t)
    
    
backTracking(0, 0, temp)

print(res)