Backtracking 백준 알고리즘 자바 1182 ‘부분수열의 합’ 문제풀이

Problem

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

Input 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

Output 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

Solution

지금까지 풀었던 다른 백트래킹과 비슷하지만 조금 다른 구조이다. 일단은 입력값이 숫자이므로 선택되는 순서와 상관이 없이 무엇을 선택했냐가 중요하다. 예를들면, 기존에는 첫번째 원소부터 시작하는 문자열과 두번째 원소부터 시작하는 문자열은 다르기때문에 dfs 메서드에서 for문을 돌려 처음 시작하는 원소를 설정해주었지만, 지금은 첫번째 원소를 선택할 것인지 말것인지만 정하면 된다.

• 부분수열을 구하는 방법으로는 지금 위치의 원소를 선택하는 방법과 선택하지 않는 방법 2가지가 있다.
• 따라서 dfs를 호출할 때, 지금 원소를 합에 더하는 부분과 dfs(v + 1, su + arr[v]) 지금 위치의 원소는 빼고 구하는 부분 dfs(v + 1, su)을 구현한다.
• for문이 없으므로 원소의 위치가 배열의 최대이면 지금까지 합이 원하는 값인지 아닌지 확인한 후, 맞으면 카운트 변수 cnt를 증가시키고 종료한다.
• 합이 0일 경우 공집합도 포함되므로 그 수를 하나 빼주고 출력한다.

Code

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int[] arr;
	static int n, s, cnt = 0;
	
	private static void dfs(int v, int su) {
		if(v == n) {
			if(su == s) cnt++;
			return;
		}

		dfs(v + 1, su + arr[v]);
		dfs(v + 1, su);
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt(); s = scan.nextInt(); arr = new int[n];
		
		for(int i = 0; i < n; i++) arr[i] = scan.nextInt();
		Arrays.sort(arr);
		
		dfs(0, 0);
		System.out.print(s == 0? --cnt : cnt);
	}
}