1182: 부분수열의 합

• depth를 1부터 N까지 변경시켜주며 dfs를 순회하여 조건을 만족시키는 부분수열들을 구함
  depth 1 -> 원소가 1개인 부분수열
  depth 2 -> 원소가 2개인 부분수열 ..
• 계속 틀리길래 원인을 못 찾고있다가 다음날 다시 보니까 수열은 원소들이 중복되는 경우가 있을 수 있다는 사실을 간과했었음
  -> 방문한 노드들을 저장하기 위해 list의 index로 check함 (visit = []/ 원소는 boolean type)

import sys

tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
N = tmp[0]; S = tmp[1]
nums = list(map(int, sys.stdin.readline()[:-1].split(' ')))
visit = [False] * N; nodes = []

count = 0
def dfs(min_idx, depth):
    global count
    if len(nodes) == depth:
        #print(nodes)
        if sum(nodes) == S:
            count += 1
        return
    for i in range(min_idx, N):
        if not visit[i]:
            nodes.append(nums[i]); visit[i] = True
            dfs(i, depth)
            nodes.pop(); visit[i] = False

for x in range(1, N+1):
    dfs(0, x)
print(count)