[백준(Baekjoon)] 1182. 부분수열의 합 (java, DFS/백트래킹)

안녕하세요. 오늘은 백준 1182. 부분수열의 합 문제를 풀어보겠습니다.

문제 링크

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

전체 풀이

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

public class Main {
    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());
        answer = 0;
        
        arr = new int[n];
        visited = new boolean[n];
        
        st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 1; i <= n; i++) {
            result = new int[i];
            dfs(i, 0, 0);
        }
        
        System.out.println(answer);
        
    }
    
    private static int s;
    private static int n;
    private static int answer;
    private static int[] arr;
    private static int[] result;
    private static boolean[] visited;
    
    private static void dfs(int depth, int now, int at) {
        //dfs를 멈추는 로직
        if(now == depth) {
            int sum = 0;
            for(int num : result) {
                sum += num;
            }
            
            if(s == sum) {
                answer++;
            }
            return;
        }
        
        for(int i = at; i < n; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                result[now] = arr[i];
                dfs(depth, now + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}

느낀점

이전에 풀었던 N과 M (2) 문제와 매우 비슷해서 큰 어려움없이 풀었다.