문제

BOJ 1182: 부분수열의 합 https://www.acmicpc.net/problem/1182

풀이

• 백트래킹을 사용하여 해결한다.
• 백트래킹에 사용할 메소드 bt(int start, int depth, int limit)의 limit 파라미터는 반복문을 사용하여 1부터 N개 까지로 해준다.(최소 1개가 집합에 들어갈 수 있도록)
• bt(int start, int depth, int limit)의 파라미터의 의미는 주석에 적어놨다.

코드

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

public class Main {
	
	static int N, S;
	static int[] arr;
	static boolean[] isChecked;
	static int[] nArr;
	static int cnt = 0;
	
	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];
		isChecked = new boolean[N];
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// i: 조합 중 몇 개를 고를지
		for(int i=1; i<=N; i++) {
			nArr = new int[i];
			bt(0, 0, i);
		}
		
		System.out.println(cnt);
	}
	
	static void bt(int start, int depth, int limit) {
		/*
		 * start: 조합을 만들어낼 때 start 앞 부분은 다시 넣을 필요 없기 때문에 그 기준을 잡아준다.
		 * depth: 탈출조건과 새로운 배열의 인덱스 역할을 한다.
		 * limit: 몇 개를 골라낼지를 정해준다.
		 */
		if(depth == limit) {
			// 배열에 넣은 값들을 모두 꺼내서 더해준다.
			int sum = 0;
			for(int val : nArr) {
				sum += val;
			}
			if(sum == S) {
				cnt++;
			}
			return;
		}
		
		for(int i=start; i<N; i++) {
			if(!isChecked[i]) {
				isChecked[i] = true;
				nArr[depth] = arr[i];
				bt(i, depth + 1, limit);
				isChecked[i] = false;
			}
			
		}
	}
	
}

정리

• 백트래킹 문제를 경험 해 봤고 이해하고 있다면 쉽게 풀 수 있다.