[백준] 1182 부분수열의 합 (JAVA)

풀이

살짝 변칙적인 백트랙킹 인듯하다. 이문제에서는 for문이 필요하지 않다. 이해는 코드를 보면 갈것이다.

 

백트랙킹 문제를 더 풀어봐야 할것 같다.

 

package com.company;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static int N;
    static int S;
    static int count=0;
    static int Sum;
    static int[] Num;

    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());
        Num = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++)
            Num[i] = Integer.parseInt(st.nextToken());

        DFS(0,0);
        if(S == 0)
            count--;
        System.out.println(count);
    }

    public static void DFS(int depth, int sum) {
        if (depth == N) {
            if (sum == S)
                count++;
            return;
        }

        //현재 인덱스 더하기
        DFS(depth+1, sum + Num[depth]);
        //현재 인덱스 더하지 않음
        DFS(depth+1, sum);
    }
}