[BOJ] 1182번 부분수열의 합 자바

문제

풀이

#브루트포스 #백트래킹 #dfs
dfs를 이용해서 원소를 더하는 경우와 더하지 않는 경우를 모두 탐색한다.
배열을 모두 돌았을 때 합이 S와 일치한다면 cnt를 증가시킨다.
만일 S가 0이라면 공집합까지 포함되어 카운트되기 때문에 -1해준다.

코드

package BOJ.bruteforce;

import java.util.*;
import java.io.*;
public class No1182_부분수열의합 {
    static int N,S;
    static int cnt=0;
    static int[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer 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());
        }

        solution(0,0);
        System.out.println(S==0? cnt-1:cnt); //공집합을 빼준다.

    }

    static void solution(int start, int sum){
        if(start==N) {
            if (sum == S) {
                cnt++;
            }
            return;
        }

        solution(start+1, sum+arr[start]);
        solution(start+1, sum);
    }
}