백준 1182 부분수열의 합

https://www.acmicpc.net/problem/1182

백트래킹 실버문제 너무행복하다 호호호

이문제를 봤을때 부분수열?

그러면 수열을 전부 구해야되는건가? 하고..
봤는데 N의값이 20이다..

수열을 직접 다구하기만해도 20개중에 10개만 쓴다해고

20p10 수가 엄청늘어난다

그래서 그냥 해당번호를 쓰고 안쓰고로 생각하면

2^20 으로 100만정도 가량이나온다..

메인로직

1. 재귀로 수열을 구한다.
2. 수열을 구할때 해당 번호가 사용하는 값일지 아닐지로 2개로 재귀를타준다.
3. 마지막 인덱스까지 도착했다면 양수의 갯수이므로 개수 count 및 값 비교를해준다..

※ 개수 카운팅을 안해주고 무지성으로 다센다음에 마지막에 안쓴것도 포함될수있으니 1빼자고 생각하면 ..
예제 입력에서 s값이 0이여서그런거지 나머지는 소용안되므로 양수카운팅 해줘야됨

코드는 다음과같다.

import java.util.*;
import java.io.*;



public class 부분수열의합 {

	static int N;
	static int S;
	static int[] array;
	static boolean[] use;
	static int answer;
	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());
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		array = new int[N];
		use = new boolean[N];
		for(int i=0;i<N;i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		answer=0;
		bt(0);
		System.out.println(answer);
	}
	public static void bt(int index) {
		if(index==N) {
			//체킹된 합 더해주기 확인하기
			int sum= 0;
			int usecheck=0;
			for(int i=0;i<N;i++) {
				
				if(use[i]) {
					usecheck++;
					sum+= array[i];
				}
			}
			if(sum==S && usecheck>0) answer++;
			return;
		}
		use[index]=true;
		bt(index+1);
		use[index]=false;
		bt(index+1);
	}

}

실버 1 드가자 드가자