백준 1182번 파이썬 문제풀이(브루트 포스 - 부분수열의 합)

---

코드1(라이브러리 이용)

import itertools

N, S = map(int, input().split())
array = list(map(int, input().split()))
count = 0

for i in range(1, N + 1):
    for j in itertools.combinations(array, i):
        if sum(j) == S:
            count += 1

print(count)

-> 워낙 쉬운 코드라 설명은 생략했다. 조합 라이브러리를 이용하면 알아서 원하는 개수만큼 원소를 뽑아주므로 반복문을 돌면서 i값을 뽑는 개수로 이용하였다.

 

---

코드2(dfs(재귀)이용)

N, S = map(int, input().split())
array = list(map(int, input().split()))
count = 0  # 개수를 셀 count값 저장
out = []  # 재귀를 돌면서 위의 array에서 m개를 뽑아서 저장할 리스트 선언


def dfs(depth, idx, m):
    global count

    if depth == m:  # 만약 out 리스트에 m개만큼 추가되었다면
        if sum(out) == S:  # out리스트의 합이 S와 같다면
            count += 1  # count값 1증가
        return

    for i in range(idx, N):  # 인자로전달받은 idx부터 N까지 돈다.(이전에 돌았던 인덱스는 안돌기 위한 장치)
        out.append(array[i])  # out에 array배열의 값 한개를 추가
        dfs(depth + 1, i + 1, m)  # 그 후 또 dfs를 돈다.
        out.pop()  # 다돌앗으면 그 값을 out리스트에서 제거


# 입력받은 array리스트에서 j(1개~N개)의 개수만큼 원소를 뽑는다.
for j in range(1, N + 1):
    dfs(0, 0, j)

print(count)  # count값 출력

-> 입력받은 array리스트 중에서 원소를 m개 뽑는 dfs를 구현한 다음 이것을 반복문을 통해서 m개를 1~N개로 인자로 넘겨주었다.