[Baekjoon 1182 / python / 실버2] 부분수열의 합

n, s = map(int, input().split())  # 숫자의 개수, 목표 숫자

numList = list(map(int, input().split()))  # 숫자 리스트

number = []  # 계산에 사용할 리스트

cnt = 0  # 경우의 수 저장할 변수

def back(start):  # 시작 인덱스 입력받기

    global cnt

    if sum(number) == s and len(number) > 0:  # 합이 s와 같고, 원소가 1개 이상일 때 ( 공집합 제외 해야 하니까 )

        cnt += 1  # 찾았으니 경우의 수 + 1

    for i in range(start, len(numList)):  # 입력받은 인덱스부터, numList의 끝까지 진행한다

        number.append(numList[i])  # 현재 인덱스에 해당하는 숫자를 계산 리스트에 추가

        print(number)

        back(i+1)  # 다음 인덱스도 계산하러 가기, 재귀 호출. # 리스트 인덱스로 바로 접근하는 게 아니라 인자로써 주기 때문에 인덱스 에러 안뜬다

                    # 그냥 다음 반복문이 실행되지 않을 뿐이다

        number.pop()  # i가 포함된 경우의 수 다 구했으니, i + 1이 포함된 경우의 수 구하러 가기

back(0)

print(cnt)

 

백트래킹이 사용되는 문제이다. 

 

수열을 입력받아서, 수열에 있는 숫자로 만들 수 있는 수열의 합이 s와 일치하는지 확인한다.

이것을 모든 경우의 수에 대해서 검사하여,  총 몇 개의 경우의 수의 합이 s와 일치하는지 출력한다.

 

백트래킹과 재귀는 아직도 많이 헷갈린다. 이해한 것 같으면서도 시간이 지나 다시 코드를 쳐보려 하면 잘 안된다.