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

본문 링크

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

value=[] ; total=0

visit=[False]*N
def BackTracking(start,value):

    global total
    if sum(value)==S and len(value)>0:
        total+=1

    for i in range(start,N):
        if not visit[i]:
            value.append(L[i])
            visit[i]=True
            BackTracking(i,value)
            value.pop()
            visit[i]=False

BackTracking(0,value)
print(total)

📌 어떻게 접근할 것인가?

백트래킹을 사용해서 접근하였습니다.
중복되지 않은 원소들을 visit 배열로 체크해준후 똑같은 값을 넣지 않았다면 원소를 넣고 재귀함수를 들어갑니다.

그리고 만약 원소의 길이가 0 이상이고 합이 $S$ 일때 total+=1 을 해줍니다.

중요한것은

• 5 0
  0 0 0 0 0

위의 답은 31 입니다. 하지만 if L[i] not in value 를 해버리면 원소를 하나만 넣게 되므로
꼭 visit=[Flase]*N 을 통해 체크해주어야 합니다. 같은 수가 들어올수 있기 때문입니다.
이후 재귀호출이 끝나면 원소를 지우고 방문처리를 되돌려놓습니다.