[JAVA] 백준 1182 부분수열의 합_브루트포스

 

 

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

 

접근 : 

 

 - 각 숫자를 더하는 경우와 더하지 않는 경우로 분리 해서 DFS 시행

 - DFS 마지막에 목표값과 동일한 경우 result + 1

 

 

 

 

코드구현 : 

 

import java.io.*;

public class Main {
    private static int n;
    private static int target;
    private static int[] nums;
    private static int result;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        target = Integer.parseInt(inputs[1]);

        nums = new int[n+1];

        inputs = br.readLine().split(" ");
        for(int i = 1 ; i <= n ; i++) nums[i] = Integer.parseInt(inputs[i-1]);

        br.close();
    }

    static void recFunc(int now, int temp_res){
        
        if(temp_res + nums[now] == target) result++;
        
        if(now == n) return;
        

        recFunc(now + 1, temp_res + nums[now]);
        recFunc(now + 1, temp_res);
    }

    public static void main(String[] args) throws IOException{
        input();
        recFunc(1, 0);
        System.out.println(result);
    }
}