[백준] 1182 부분수열의 합 - Java

 

 

 

재귀함수를 사용해 백트래킹을 구현해서 풀 수 있는 문제이다.

 

백트래킹 알고리즘에서 가장 중요한 부분은 재귀함수의 올바른 정의이다.

재귀함수와 반복문잉 본직적인 차이가 없음을 이해하고 재귀함수를 정의하자..

 

재귀적 스타일에 익숙해 지는 게 중요하다. 

 

종료 조건 명시해두고, 인덱스를 하나씩 늘려 가며 "이렇게 작성하면 모든 경우를 셀 수 있겠다." 라는 믿음을 가지자.

 

 

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

public class Main {

	static int N;
	static int S;
	static int ans;

	static int arr[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());

		arr = new int[N + 1];

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i < N + 1; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		solve(1, 0);

		if (S == 0) {
			ans--;
		}

		System.out.println(ans);

	}

	static void solve(int K, int cumulative) {
		
		if (K == N + 1) {
			if (cumulative == S) {
				ans++;
			}
		} else {
			solve(K + 1, cumulative + arr[K]);
			solve(K + 1, cumulative);
		}

	}

}