[백준, 1182번] 부분수열의 합 (브루트 포스, 재귀, 백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 부분수열의 합" 문제는 정수 N개 수열과 정수S가 주어졌을 때 해당 수열의 부분 수열에서 더하여 정수 S를 만들 수 있는 경우의 수를 구하는 문제입니다.

 

위와 같이 정수 S가 0일 때, 수열에서 0을 만들 수 있는 부분수열은 [-3, -2, 5]입니다.

 

이 부분수열을 찾기 위해서는 수열의 첫 번째 원소부터 차례대로 탐색하며, 각 원소를 포함할지 말지를 결정하여 부분수열을 구성해 나가야 합니다.

 

즉, 각 원소에 대해 포함할지 말지를 결정해야 하며, 이 과정은 백트래킹(Backtracking) 방식으로 해결할 수 있습니다.

---

전체 코드

 

부분 수열을 구할 때, 각 원소를 "포함"하거나 "포함하지 않음" 두 가지 선택합니다.

 

재귀 함수에서 중요한 부분 중 하나인 탈출 조건은 idx(인덱스)가 수열의 길이와 같을 때, 즉, 수열을 전부 순회했을 때 입니다. 이때, 수열을 모두 탐색한 후, 현재까지 더한 값이 타겟 넘버(S)와 같다면 경우의 수를 증가시킵니다.

 

이때 중요한 점은 아무 수열도 포함하지 않는 경우가 있을 수 있다는 점입니다.

5 0
-7 -3 -2 5 8

 

첫 번째 정수인 -7부터 포함할지 포함하지 않을지 결정합니다. 이때 -7을 포함하지 않는 경우, 부분 수열은 []가 되고, 부분 합은 0이 됩니다.

 

현재 타겟 넘버 S가 0이므로, 부분 합이 0인 경우는 하나의 유효한 경우로 취급됩니다. 따라서 S가 0일 때는 경우의 수에서 1을 빼줘야 합니다.

 

ps

처음에는 백트래킹 + 수열 문제이기 때문에 visited 배열을 사용하여 방문여부를 체크하려고 했습니다.

 

그러나 결과적으로는 visited배열은 필요가 없습니다. 왜냐하면 부분 수열을 구할 때, 각 원소를 "포함"하거나 "포함하지 않음" 두 가지 선택을 하게 되는데, 이 선택 자체가 중복된 탐색을 발생시키지 않기 때문입니다.

 

for문을 사용하여 모든 인덱스를 반복하는 대신, 재귀 호출로 자연스럽게 각 수를 선택하는 방식으로 구현할 수 있습니다.

 

visited 배열을 사용하여 방문 여부를 체크하는 궁극적인 이유는 중복된 탐색을 방지하기 위함인데, 재귀적 탐색에서 각 선택이 독립적이기 때문에 중복 탐색이 발생하지 않아 visited 배열이 필요하지 않습니다.