BOJ :: 1182(부분 수열의 합)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
package backjun;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class BOJ_1182_부분수열의합_백트래킹 {
static int aim=0;
static int[] arr;
static int answer = 0;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
aim = 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<=arr.length; i++) {
make(-1, arr.length-1, i, 0, new HashSet<>());
}
System.out.println(answer);
}
static void make(int a, int b, int c, int d, HashSet<Integer> keySet) {
if(c==d) {
long temp =0;
for(int k : keySet) {
temp+=arr[k];
}
if(temp==aim) {
answer+=1;
}
return ;
}
for(int i=a+1; i<=b; i++) {
HashSet<Integer> newKeySet = new HashSet<>(keySet);
newKeySet.add(i);
make(i, b, c, d+1, newKeySet);
}
}
}
|
cs |
'알고리즘' 카테고리의 다른 글
특정거리의 도시찾기 (0) | 2020.11.07 |
---|---|
멀쩡한사각형 (0) | 2020.11.07 |
알고리즘108 :: 구간합 (JAVA) (0) | 2020.09.30 |
알고리즘107 :: 투포인트 - BOJ_수들의합2 (0) | 2020.09.28 |
알고리즘106 :: BOJ_11726_2XN타일링 (0) | 2020.09.27 |
댓글
이 글 공유하기
다른 글
-
특정거리의 도시찾기
특정거리의 도시찾기
2020.11.07 -
멀쩡한사각형
멀쩡한사각형
2020.11.07 -
알고리즘108 :: 구간합 (JAVA)
알고리즘108 :: 구간합 (JAVA)
2020.09.30 -
알고리즘107 :: 투포인트 - BOJ_수들의합2
알고리즘107 :: 투포인트 - BOJ_수들의합2
2020.09.28