[Python] 1182. 부분 수열의 합

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

1182번: 부분수열의 합

 

접근법

• 재귀를 통해 생성가능한 조합을 모두 뽑아내고자 했음.
• algorithm 라이브러리의 combination을 써도 된다고 함.

def make_sum(idx, sum):
    global count
    if idx >= N:
        return

    sum += arr[idx] # sum과 S를 비교하기 전에 arr[idx]를 하나라도 더해야만, 원소가 하나도 없는 것을 고려할 수 있음

    if sum == S:
        count += 1

    make_sum(idx + 1, sum)
    make_sum(idx + 1, sum - arr[idx])


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

make_sum(0, 0)
print(count)

---

처음 생각했던 알고리즘의 문제점(틀린이유)

try1

• 부분 수열이 아니라 연속적인(?) 수열만을 생성함.
• 즉 [1,2,3] 이 있을 때 [1],[2],[3],[1,2],[2,3],[1,2,3]만을 생성하고 [1,3]을 뽑아내지 못함.

arr = []
visited = []
N, S = 0, 0
count = 0
def make_sum(idx, sum):
    global count
    if idx >= N:
        return
    if sum == S:
        count += 1
    sum += arr[idx]
    make_sum(idx + 1, sum)

def main():
    N, S = map(int,input().split())
    arr = map(int, input().split())
    make_sum(arr, 0, S)

if __name__ == "__main__":
    main()

 

사용된 알고리즘

브루트포스, 백트래킹