import java.io.*;
import java.util.*;
public class Main {
static int N;
static int S;
static int ans = 0;
static int[] arr;
static StringTokenizer st;
public static void backtracking(int idx, int sum) {
if(idx == N) {
if(sum == S) {
ans++;
}
return;
}
backtracking(idx+1, sum);
backtracking(idx+1, sum+arr[idx]);
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
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) ans--;
System.out.println(ans);
}
}
이 문제의 핵심은 재귀로 경우의 수를 찾을 때 해당 원소를 더하지 않는 경우와 원소를 더하는 경우를 나누는 것이다.
이런식으로 해당 원소마다 2가지의 경우의 수로 가지를 늘려 이진 트리 구조가 나오게 된다.
그러다가 마지막 원소까지 경우의 수를 구했을 때 해당 합이 S와 같을 경우에는 카운트를 올려주면 된다.
그리고 마지막에 S가 0일 경우에는 공집합이 카운트에 하나가 포함이 되므로 빼주고 출력하면 된다.
'Dev > PS' 카테고리의 다른 글
[백준] 14889 스타트와 링크 java (0) | 2022.02.08 |
---|---|
[백준] 10819 차이를 최대로 java (0) | 2022.02.07 |
[백준] 1009 분산 처리 java (0) | 2022.01.27 |
[백준] 15686 치킨 배달 java (1) | 2022.01.26 |
[백준] 1920 수 찾기 java (0) | 2022.01.20 |