[SWEA] 2817. 부분 수열의 합

문제

A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

풀이방법

DFS(깊이 우선 탐색)로 공집합을 제외한 모든 부분집합을 구하고 부분집합의 합이 k와 일치하는 계수를 구한다.

 

소스코드

package samsung;

import java.util.*;

public class s_2817 {
	static int n;
	static int k;
	static int[] a;
	static int[] visit;
	static int cnt;
	
	public static void dfs(int x, int sum) {
		visit[x] = 1;
		sum += a[x];
		if(sum == k)
			cnt++;
		for(int i = x; i < n; i++) {
			if(visit[i] == 0) {
				dfs(i, sum);
				visit[i] = 0;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		
		for(int t = 1; t <= test; t++) {
			n = sc.nextInt();
			k = sc.nextInt();
			a = new int[n];
			visit = new int[n];
			cnt = 0;
			
			for(int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					visit[j] = 0;
				}
				dfs(i, 0);
			}
			System.out.println("#" + t + " " + cnt);
		}
	}
}