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

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

1182번: 부분수열의 합

 

이 문제를 풀면서 백트래킹과 DFS의 차이가 헷갈렸다.

중간에 아닌것 같으면 되돌아가는 것이 백트래킹, 끝까지 가는 것이 DFS라고 하는데 다른 풀이를 보면 거의 같은 코드인데 어떤 사람은 백트래킹, 어떤 사람은 DFS라고 한다.... 더 헷갈린다.

 

    static public void dfs(int sum, int index) {
        if (index >= N)
            return;
        if (sum + a[index] == S) // 합이 같은 경우
            result++;

        // 더하는 경우
        dfs(sum + a[index], index + 1);

        // 안 더하는 경우
        dfs(sum, index + 1);
    }

index는 더할 배열의 인덱스이다. 모든 인덱스를 확인했다면 그만한다.

합이 같은 경우 result를 더해주고 현재 인덱스의 배열을 더하는 경우, 더하지 않는 경우로 나눈다.

 

전체 코드

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

public class Main {
    static int N, S, result = 0;
    static int[] a;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;

        input = br.readLine();
        StringTokenizer st = new StringTokenizer(input);
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        input = br.readLine();
        st = new StringTokenizer(input);
        a = new int[N];

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

        dfs(0, 0);
        System.out.println(result);

    }

    static public void dfs(int sum, int index) {
        if (index >= N)
            return;
        if (sum + a[index] == S) // 합이 같은 경우
            result++;

        // 더하는 경우
        dfs(sum + a[index], index + 1);

        // 안 더하는 경우
        dfs(sum, index + 1);
    }
}