public class Main{ static int S; static int cnt = 0; static void go(int[] a, HashSet<Integer> check, int currIdx){ int sum = 0; for(int e: check){ sum+=e; }
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); S = sc.nextInt(); int a[] = new int[N]; for(int i = 0; i<N;i++){ a[i] = sc.nextInt(); } HashSet<Integer> check = new HashSet<>();
quki 5년 전
문제 조건에서 중복된 수가 입력돼서는 안되는데,
중복된 수가 테스트 케이스에 있는 것 같습니다.
그래서 Set 자료구조를 쓰면 13%에서 틀렸다고 나옵니다.
import java.util.HashSet;
import java.util.Scanner;
public class Main{
static int S;
static int cnt = 0;
static void go(int[] a, HashSet<Integer> check, int currIdx){
int sum = 0;
for(int e: check){
sum+=e;
}
if(sum == S){
cnt++;
}
for(int next = currIdx+1; next<a.length; next++){
check.add(a[next]);
go(a, check, next);
check.remove(a[next]);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
S = sc.nextInt();
int a[] = new int[N];
for(int i = 0; i<N;i++){
a[i] = sc.nextInt();
}
HashSet<Integer> check = new HashSet<>();
for(int i = 0; i<N; i++){
check.add(a[i]);
go(a, check, i);
check.remove(a[i]);
}
System.out.println(cnt);
}
}