[백준 풀이_Java] 1182 부분수열의 합 (실버2)

 

dfs 함수 안에서 반복문만 쓰는 문제만 풀다가 포함 or 미포함 여부를 재귀로 타고 들어가는 문제를 만나서

 

결국 다른 블로그와 영상을 보며 이해했다.

 

개수와 상관 없이 주어진 값을 조합해서 나온 결과를 확인할 때는, 해당 인덱스의 값을 포함할 것인지 아닌지를

 

코드로 구현하면 되겠다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int S;

    static int result;

    static int[] arrNums;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        S = Integer.parseInt(input[1]);
        arrNums = new int[N];
        result = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            arrNums[i] = Integer.parseInt(st.nextToken());
        }
        
        recur(0, 0, 0);
        System.out.println(result);

    }


    static void recur(int index, int sum, int cnt){
        // if 0
        if(index == N){ // 전체를 다 돌았으면 리턴할건데,
            if(sum == S && cnt > 0) { // 값을 확인하고 내보내준다
                result++;
            }
            return;
        }

        recur(index+1, sum + arrNums[index], cnt+1); // 포함하는 경우
        recur(index+1, sum, cnt); // 포함하지 않는 경우

    }

}