[BOJ_1182 | DFS backtracking] 부분집합의 합

풀이

DFS 백트래킹을 이용해서 풀 수 있는 문제였다.

부분집합의 모든 경우를 헤아린다든지 하는 문제에서는 DFS를 통해

재귀함수가 알아서 처리하도록 하는 편이 코딩하는 데 더 간편한 것 같다.

이 문제를 풀 때 주의해야 할 점은

탐색을 하다가 S값을 찾았다고 해서 서둘러 탐색을 종료해서는 안된다는 것이다.

예를 들어 S 값이 10이라고 할 때 

1, 2, 3, 4 를 순서대로 탐색하고 '아 10이니까 이제 종료하고 다른 케이스를 살펴봐야지'

하면 안된다는 의미인데, 왜냐하면 Array의 원소 중에 음수인 경우가 있으므로

1, 2, 3, 4, -5, 5인 경우도 합이 10이 되는 케이스가 있을 수 있기 때문이다.

따라서 S값을 찾았을 때는 counter의 값만 증가시켜주고 탐색을 계속해야 한다.

소스코드

import java.util.*;
import java.io.*;
public class BOJ_1182 {

    static int n, s, cnt;
    static int[] arr;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        arr = new int[n]; cnt = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){ arr[i] = Integer.parseInt(st.nextToken());}
        //implement DFS
        for(int i=0;i<n;i++){ DFS(i, 0); }

        bw.write(cnt+"\n");
        bw.flush();
        bw.close();
    }

    public static void DFS(int idx, int sum){
        sum += arr[idx];
        if(sum == s) cnt++;
        for(int i=idx+1;i<n;i++){
            if(isValid(idx+1)) DFS(i, sum);
        }
    }
    public static boolean isValid(int idx){
        if(idx>=0 && idx<n) return true;
        return false;
    }
}