[BOJ] 1182 부분 수열의 합 - JAVA

1. 문제

1182번: 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  부분집합을 이용했다.

2.  만약 idx가 N이라면(범위를 벗어났다면) 종료한다.

3.  만약 지금까지의 합계+현재idx숫자가 S와 동일하다면 카운트를 +1한다.

4.  부분집합 재귀가 모두 끝났다면 cnt를 출력한다.

* 꼭 2번 후에 3번을 체크해야 한다.

import java.io.*;
import java.util.*;

public class BOJ_1182_부분수열의합 {
   static int[] input;
   static int N,S,cnt;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      S = Integer.parseInt(st.nextToken());
      input = new int[N];
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) input[i] = Integer.parseInt(st.nextToken());
      find(0,0);
      System.out.println(cnt);
   }
   private static void find(int idx,int sum){
      if(idx==N) return;
      if(sum+input[idx]==S) cnt++;
      find(idx+1,sum+input[idx]);
      find(idx+1,sum);
   }
}

---

3. 결과

재귀 기저조건 순서 때문에 몇 번 틀렸다.