[백준][파이썬] 1182 부분수열의 합

핵심

1. visited 사용할때 not in stack 이 두개의 차이는 중복된 숫자를 체크 가능한지 여부이다.

2. depth를 다르게 줘야할때는 함수 밖에서 depth를 다르게 설정해서 줄 수 있다.

N, S = map(int, input().split())
lit = list(map(int, input().split()))
count = 0
visited = [False] * N

def per(idx, depth, stack, max):
    global count
    if depth == max:
        total = 0
        for sum in stack:
            total += sum
        if total == S:
            count += 1

    for i in range(idx, N):
        if visited[i] ==False:
            visited[i] =True
            stack.append(lit[i])
            per(i + 1, depth + 1, stack, max)
            stack.pop()
            visited[i] =False

for i in range(1, N):
    per(0, 0, [], i)
summ = 0
for i in lit:
    summ += i
if summ == S:
    count += 1

print(count)

 

------------------------------------------------2021 - 01 - 18 풀이 ------------------------------------------------------------

 

코드 자체가 간결해진 가장 큰 이유는 depth 설정하는 부분을 따로 외부에서 두지 않았다. 모든 집합의 합이기 때문에 

재귀함수의 if문을 이용했다.

 

재귀함수 문제를 풀 때 return 이 큰 영향을 줄 수 있으니 항상 주의하자!

 

n,target = map(int, input().split(" "))
numlist = list(map(int, input().split(" ")))
check = [0] * n
ans = 0
def recu(num, g, s,check,cnt):
    global ans
    if 0 <len(s) < num+1:
        if sum(s) == target:
            ans += 1


    for i in range(cnt, num):
        if check[i] == False:
            check[i] = True
            recu(num,g,s+[g[i]],check,i+1)
            check[i] = False
    return

recu(n,numlist,[],check,0)
print(ans)