백준 1182 부분수열의 합 (Silver2)

정답코드

import java.util.*;

public class Main {
    static int N;
    static int S;
    static int[] ary;
    static int result = 0;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        ary = new int[N];
        for(int i = 0; i < N; i++){
            ary[i] = sc.nextInt();
        }
        compute(0,0);
		//구하고 싶은 합이 0일 때 부분합이 0인 경우와 아무것도 더하지 않아 0인 것을 구분
        if (S==0)result--;
        System.out.println(result);
    }

    public static void compute(int depth, int sum){

        if(depth==N){
            if(sum==S)result++;
            return;
        }

		//부분합을 구할 때 지금 element를 부분합에 포함하고 싶은 경우
        compute(depth+1,sum+ary[depth]);
		
        //지금 element를 부분합에 포함하지 않을 경우 
		//이번 depth에서의 index를 더하지 않고 뒤로 넘김 
        compute(depth+1,sum);
    }
}

전략

• 숫자들을 순회하면서 현재 index의 숫자를 합에 포함시키는 경우와 포함시키지 않는 경우를 나눠서 DFS를 따로 보내준다

• 두 갈래 길로 나눠서 DFS를 보내는 경우 Binary Tree 형식으로 경우의 수가 나눠진다