[백준 | 1182] 부분수열의 합 - Java

📃 제출

import java.util.Scanner;

public class Main {
    static int answer = 0;
    static int N;
    static int S;
    static int[] nums;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        S = sc.nextInt();

        nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }

        dfs(0, 0);
        if (S == 0) answer--;

        System.out.println(answer);
    }

    public static void dfs(int index, int sum) {
        if (index == N) {
            if (sum == S) {
                answer++;
            }
            return;
        }

        dfs(index + 1, sum);
        dfs(index + 1, sum + nums[index]);
    }
}

✏ 풀이

핵심 아이디어:

1. 각 원소를 포함하거나 포함하지 않는 두 가지 선택을 가지면서, 모든 가능한 부분수열을 탐색합니다.
2. 재귀적으로 각 원소를 선택한 경우와 선택하지 않은 경우를 처리하여, 모든 경우의 수를 탐색합니다.
3. 탐색 과정에서 부분수열의 합이 S와 같아지는 경우를 카운트합니다.

코드 설명

1. DFS 함수 (dfs):
   • 각 재귀 호출에서 현재 인덱스 index의 원소를 포함할지 여부를 결정합니다.
   • 원소를 포함하지 않는 경우, 다음 인덱스로 넘어가고 (dfs(index + 1, sum)).
   • 원소를 포함하는 경우, 현재 합계에 원소를 더한 후 다음 인덱스로 넘어갑니다 (dfs(index + 1, sum + nums[index])).
2. 기저 조건:
   • index == N이 되면 모든 원소를 다 고려한 것이므로, 현재 합계가 S와 같은지 확인하여 카운트합니다.
3. 결과 조정:
   • 만약 S가 0인 경우, 아무것도 선택하지 않은 경우도 포함될 수 있으므로, 이 경우를 제외하기 위해 최종적으로 answer에서 1을 뺍니다

 

arr = [-7, -3, -2, 5, 8]
dfs(index, sum)

dfs(0, 0)  // 시작점, 현재 합계 0
├── dfs(1, 0)    // 원소 -7을 포함하지 않음
│   ├── dfs(2, 0)    // 원소 -3을 포함하지 않음
│   │   ├── dfs(3, 0)    // 원소 -2를 포함하지 않음
│   │   │   ├── dfs(4, 0)    // 원소 5를 포함하지 않음
│   │   │   │   ├── dfs(5, 0)    // 원소 8을 포함하지 않음 -> 끝(합계 0)
│   │   │   │   └── dfs(5, 0 + 8)    // 원소 8을 포함 -> 끝(합계 8)
│   │   │   └── dfs(4, 0 + 5)    // 원소 5를 포함 -> 합계 5
│   │   │       ├── dfs(5, 5)    // 원소 8을 포함하지 않음 -> 끝(합계 5)
│   │   │       └── dfs(5, 5 + 8)    // 원소 8을 포함 -> 끝(합계 13)
│   │   └── dfs(3, 0 + (-2))    // 원소 -2를 포함 -> 합계 -2
│   │       ├── dfs(4, -2)    // 원소 5를 포함하지 않음 -> 합계 -2
│   │       │   ├── dfs(5, -2)    // 원소 8을 포함하지 않음 -> 끝(합계 -2)
│   │       │   └── dfs(5, -2 + 8)    // 원소 8을 포함 -> 끝(합계 6)
│   │       └── dfs(4, -2 + 5)    // 원소 5를 포함 -> 합계 3
│   │           ├── dfs(5, 3)    // 원소 8을 포함하지 않음 -> 끝(합계 3)
│   │           └── dfs(5, 3 + 8)    // 원소 8을 포함 -> 끝(합계 11)
│   └── dfs(2, 0 + (-3))    // 원소 -3을 포함 -> 합계 -3
│       ├── dfs(3, -3)    // 원소 -2를 포함하지 않음 -> 합계 -3
│       │   ├── dfs(4, -3)    // 원소 5를 포함하지 않음 -> 합계 -3
│       │   │   ├── dfs(5, -3)    // 원소 8을 포함하지 않음 -> 끝(합계 -3)
│       │   │   └── dfs(5, -3 + 8)    // 원소 8을 포함 -> 끝(합계 5)
│       │   └── dfs(4, -3 + 5)    // 원소 5를 포함 -> 합계 2
│       │       ├── dfs(5, 2)    // 원소 8을 포함하지 않음 -> 끝(합계 2)
│       │       └── dfs(5, 2 + 8)    // 원소 8을 포함 -> 끝(합계 10)
│       └── dfs(3, -3 + (-2))    // 원소 -2를 포함 -> 합계 -5
│           ├── dfs(4, -5)    // 원소 5를 포함하지 않음 -> 합계 -5
│           │   ├── dfs(5, -5)    // 원소 8을 포함하지 않음 -> 끝(합계 -5)
│           │   └── dfs(5, -5 + 8)    // 원소 8을 포함 -> 끝(합계 3)
│           └── dfs(4, -5 + 5)    // 원소 5를 포함 -> 합계 0
│               ├── dfs(5, 0)    // 원소 8을 포함하지 않음 -> 끝(합계 0)
│               └── dfs(5, 0 + 8)    // 원소 8을 포함 -> 끝(합계 8)
└── dfs(1, 0 + (-7))    // 원소 -7을 포함 -> 합계 -7
    ├── dfs(2, -7)    // 원소 -3을 포함하지 않음 -> 합계 -7
    │   ├── dfs(3, -7)    // 원소 -2를 포함하지 않음 -> 합계 -7
    │   │   ├── dfs(4, -7)    // 원소 5를 포함하지 않음 -> 합계 -7
    │   │   │   ├── dfs(5, -7)    // 원소 8을 포함하지 않음 -> 끝(합계 -7)
    │   │   │   └── dfs(5, -7 + 8)    // 원소 8을 포함 -> 끝(합계 1)
    │   │   └── dfs(4, -7 + 5)    // 원소 5를 포함 -> 합계 -2
    │   │       ├── dfs(5, -2)    // 원소 8을 포함하지 않음 -> 끝(합계 -2)
    │   │       └── dfs(5, -2 + 8)    // 원소 8을 포함 -> 끝(합계 6)
    │   └── dfs(3, -7 + (-2))    // 원소 -2를 포함 -> 합계 -9
    │       ├── dfs(4, -9)    // 원소 5를 포함하지 않음 -> 합계 -9
    │       │   ├── dfs(5, -9)    // 원소 8을 포함하지 않음 -> 끝(합계 -9)
    │       │   └── dfs(5, -9 + 8)    // 원소 8을 포함 -> 끝(합계 -1)
    │       └── dfs(4, -9 + 5)    // 원소 5를 포함 -> 합계 -4
    │           ├── dfs(5, -4)    // 원소 8을 포함하지 않음 -> 끝(합계 -4)
    │           └── dfs(5, -4 + 8)    // 원소 8을 포함 -> 끝(합계 4)
    └── dfs(2, -7 + (-3))    // 원소 -3을 포함 -> 합계 -10
        ├── dfs(3, -10)    // 원소 -2를 포함하지 않음 -> 합계 -10
        │   ├── dfs(4, -10)    // 원소 5를 포함하지 않음 -> 합계 -10
        │   │   ├── dfs(5, -10)    // 원소 8을 포함하지 않음 -> 끝(합계 -10)
        │   │   └── dfs(5, -10 + 8)    // 원소 8을 포함 -> 끝(합계 -2)
        │   └── dfs(4, -10 + 5)    // 원소 5를 포함 -> 합계 -5
        │       ├── dfs(5, -5)    // 원소 8을 포함하지 않음 -> 끝(합계 -5)
        │       └── dfs(5, -5 + 8)    // 원소 8을 포함 -> 끝(합계 3)
        └── dfs(3, -10 + (-2))    // 원소 -2를 포함 -> 합계 -12
            ├── dfs(4, -12)    // 원소 5를 포함하지 않음 -> 합계 -12
            │   ├── dfs(5, -12)    // 원소 8을 포함하지 않음 -> 끝(합계 -12)
            │   └── dfs(5, -12 + 8)    // 원소 8을 포함 -> 끝(합계 -4)
            └── dfs(4, -12 + 5)    // 원소 5를 포함 -> 합계 -7
                ├── dfs(5, -7)    // 원소 8을 포함하지 않음 -> 끝(합계 -7)
                └── dfs(5, -7 + 8)    // 원소 8을 포함 -> 끝(합계 1)