🔗 Problem

https://www.acmicpc.net/problem/1182

👩‍💻 Code - Bit Mask

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

// 부분수열의 합

public class BJ1182 {
	
	static int n;
	static int s;
	static int[] arr;
	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];

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		for(int i = 1; i <= Math.pow(2, n) - 1; i++) {
			
			int total = sumIntegers(i);
			if(total == s) cnt++;
		}
		
		System.out.println(cnt);
	}
	
	private static int sumIntegers(int bit) {
		int total = 0;
		for(int i = 0; i < n ; i++) {
			int mask = bit & (1 << i);		// 부분수열 index를 비트로 표현하여 1인 경우만 값을 더함
			if(mask > 0) {
				total += arr[i];
			}
		}
		return total;
	}

}

👩‍💻 Code - Back Tacking

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

// 부분수열의 합

public class BJ1182_2 {
	
	static int n;
	static int s;
	static int[] arr;
	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];

		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		backTracking(0, 0);
		
		if(s == 0) {
			System.out.println(cnt - 1);		// 공집합인 경우 제외
		}
		else {
			System.out.println(cnt);
		}

	}
	
	private static void backTracking(int depth, int total) {

		if(depth == n) {
			if(total == s) cnt++;
			return;
		}

		backTracking(depth + 1, total);					// 선택하지 않는 경우
		backTracking(depth + 1, total + arr[depth]);	// 선택하는 경우
	}
}

📌 Note

아이디어

• Back tracking으로 풀 때, backTracking()에 for문을 하나 더 둬서 현재 위치 기준 다음 인덱스부터 탐색하도록 구현하였는데(pruning) 반례가 존재하여 풀이법을 바꾸었다. (22.03.30기준 반례 unsolved..)
• 선택 유무를 단순히 total에 더하느냐 or 마느냐 로 처리하여 그냥 가지를 늘려가는 방법이 현명했다.

• Bitmask로 문제를 처음 풀어봤는데 괜찮은 스킬인 것 같다.
• 위 풀이에서는 BackTracking이 Bitmask보다 더 빠르다.