[백준] Silver II. 부분수열의 합

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

 

알고리즘

• 백트래킹

풀이

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


public class Main {
    static int n, s;
    static int [] arr;
    static int count = 0;
    static boolean [] visited;
    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());
        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());
        }

        dfs(0, 0);
        if (s == 0) count -= 1;
        System.out.println(count);
    }

    public static void dfs(int sum, int depth) {
        if (depth == n) {
            if (sum == s) {
                count++;
            }
            return;
        }
        dfs(sum + arr[depth], depth + 1); // 배열에서 값을 더하면서 넘어가는 경우
        dfs(sum, depth + 1); // 배열에서 값을 고르지 않은 경우
    }
}

회고

 

문제를 풀면서 재귀의 종료 조건을 단순하게 sum == s일때만 count를 늘려주는 식으로 구현했다. 

 

5 0
-7 -3 -2 5 8

 

위 방법의 풀이는 단순히 [-3,-2,5] 이 경우에 합이 0이 되니 그렇게 한건데 다른 풀이를 참고하니 무조건 depth == n까지 돌면서, 배열의 값을 선택할 때와 선택하지 않을 때를 나눠서 백트래킹을 돌렸다.

 

즉, [-3,2,5]가 아닌, [0,-3,2,5,0] 이런식으로 되는 것이다. 그리고 s가 0이라면, 공집합이 포함되기 때문에 count - 1을 해 주었다.