[SWEA]가능한 시험 점수(3752번, 자바)HashSet, ArrL, 완전탐색★★★

ㄴ시간초과 

package samsung01;

import java.util.*;

class Solution
{

	static long answer=0;
	static int N;
	static boolean[] visit;
	static int[] d;
	static HashSet<Integer> hs;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		hs=new HashSet<>();
	
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			N=sc.nextInt();
			d=new int[N];
			for(int i=0;i<N;i++) d[i]=sc.nextInt();
			dfs(0,0);
			
			System.out.println("#"+ test_case+" "+hs.size());
			
		}
	}
	
	static void dfs(int idx, int sum) {
		if(idx==N) {
			hs.add(sum);
			return;
		}
		
		dfs(idx+1, sum+d[idx]);
		dfs(idx+1, sum);
		
	}

}

 

 

 

3개 o 시간초과 

package samsung01;

import java.util.*;

class Solution
{

	
	static int N;
	static int[] d;
	static HashSet<Integer> hs;
	static int[] score;
	static ArrayList<Integer> arr;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			arr=new ArrayList<>();
			N=sc.nextInt();
			d=new int[N];
			for(int i=0;i<N;i++) d[i]=sc.nextInt();
			
			arr.add(0);
			arr.add(d[0]);
			
			
			for(int i=1;i<N;i++) {
				int size=arr.size();
				for(int j=0;j<size;j++) {
					int score=arr.get(j)+d[i];
					if(!arr.contains(score)) arr.add(score);
				}
			}
			System.out.println("#"+test_case+" " +arr.size());
		}
	}
}

 

 

1번과 2번을 조합

package samsung01;

import java.util.*;

class Solution
{

	
	static int N;
	static int[] d;
	static HashSet<Integer> hs;
	static ArrayList<Integer> arr;
	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			
			arr=new ArrayList<>();
			N=sc.nextInt();
			d=new int[N];
			for(int i=0;i<N;i++) d[i]=sc.nextInt();
			hs=new HashSet<>();
			
			hs.add(0);
			arr.add(0);
			dfs(0);
			
			System.out.println("#"+test_case+" " +arr.size());
		}
	}
	static void dfs(int count) {
		if(count==N) return;
		
		int len=arr.size();
		for(int i=0;i<len;i++) {
			if(!hs.contains(arr.get(i)+d[count])) {
				hs.add(arr.get(i)+d[count]);
				arr.add(arr.get(i)+d[count]);
			}
		}
		dfs(count+1);
	}
}