[백준 01182] 부분수열의 합 [Python]

문제

1182번: 부분수열의 합

---

풀이

N개의 정수에 대한 조합 가능한 모든 부분 수열을 찾고, 부분 수열의 합이 S와 일치하는 경우를 찾아야 한다.

크기가 양수인 부분 수열에 대한 합비교 이므로 S가 0일 때 부분 수열의 길이가 0인 경우는 제외해야 한다. 

 

combinations 사용 버전

N개의 정수로 이루어진 수열에 대해 1 ~ N개로 생성할 수 있는 조합을 전부 생성해 합을 비교하는 방법이다.

가장 짧고 간결한 방법이다.

부분 수열의 합이 S와 일치한다면 갯수를 의미하는 1을 반환해주어 합을 구하면 된다.

 

 

combinations 미사용 버전

위의 방식대로 결국은 조합을 구하는 문제다.

때문에 탐색 중 부분 수열의 합이 S와 일치한 경우 탐색을 중단하는 것이 아니라 다른 조합을 찾아야 한다.

N개의 요소까지 전부 탐색했고, 부분합( res )이 S와 일치하는 경우에만 1을 반환해주자.

 

요소를 탐색 중이라면, 현재 요소를 포함/미포함 하는 경우에 대해 분기를 나누어 탐색해주자.

위 탐색과정은 부분수열의 길이가 0일 때, S가 0인 경우도 하나의 횟수로 계산한다.

S가 0인 경우에만 위와 같은 오차가 있으니 결과를 출력할 때 예외처리 하자.

---

소스코드

보기