[Java] Baekjoon1182: 부분수열의 합

부분수열의 합

2 초

256 MB

46172

21277

13612

44.205%

문제

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

입력

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

출력

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

풀이

dfs의 기본적인 정의를 활용해 풀이하려고 했습니다.

 

조건

크기가 양수일 것 = 최소한 하나라도 골라야합니다.

 

부분집합

N이 20개 이하이므로 N개의 원소 하나하나의 입장에서 선택할수도, 선택하지 않을 수도 있습니다.

 

재귀 구현

재귀 메소드 내에서 다음 재귀를 호출할 때 2개의 메소드를 호출합니다.

1) 현재 원소를 선택하고 다음 원소로 넘어가는 메소드

2) 현재 원소를 선택하지 않고 다음 원소로 넘어가는 메소드

그리고 합이 S가 되는 순간 카운트해주는 방식을 사용합니다.

 

주의사항

중복 카운트가 발생할 수 있기 때문에 중간 중간에 카운트하지 않고 끝점에 도달했을 때 카운트 해주어야 합니다.

 

전체 코드

import java.util.*;

public class Main {
	static int N,S,cnt,arr[];
	
	static void dfs(int idx, int sum, int select) { // i 현재 index
		if(idx==N && sum==S && select!=0) {
			cnt++;
			return;
		}
		if(idx==N) return; // 배열 끝에 도달하면 종료
		
		dfs(idx+1,sum+arr[idx],select+1); //현재 원소를 선택하고 보내기
		dfs(idx+1,sum,select); //현재 원소를 선택하지 않고 보내기
		
	}
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	S = sc.nextInt();
	cnt = 0; // 카운트
	arr = new int[N];

	
	//입력 받기
	for(int i = 0; i<N; i++) {
		arr[i] = sc.nextInt();
	}
	
	dfs(0,0,0);
	System.out.println(cnt);
}
}