[수학] 백준 1182번 부분수열의 합 with python

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

n, s = map(int, input().split())
lst = list(map(int, input().split()))

pair = []
cnt = 0

def btracking(start):
    global cnt

    if sum(pair) == s and len(pair) > 0:
        cnt += 1

    for i in range(start, n):
        pair.append(lst[i])
        btracking(i + 1)
        pair.pop()

btracking(0)
print(cnt)

저번에 풀었던 n과m과 다르게 [1, 3]과 [3, 1]은 똑같다고 보는 중복을 허용하지 않는 combination문제였다.
코드의 차이점은 중복을 허용했던 permutation은 반복문이 처음부터 돌지만 중복을 허용하지 않는 combination은 반복문을 특정 숫자 이후에만 돌아가게 함으로써 그 이전 숫자들은 다시 들어오지 못하게 하였다.