[백준 1182] 부분수열의 합 (Java)

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

 

접근 방법

백트래킹 방법을 이용했다. dfs와 유사하게 깊이 우선으로 탐색을 하되, 조건에 충족하지 않으면 이전 깊이로 돌아가 이어서 진행하는 방식으로 구현하였다.

 

입력값으로 받은 수열을 배열로 만들고 순차적으로 탐색을 하는데 깊이 들어갈 때 마다

해당 깊이의 값을 포함하고 다음 깊이로 재귀

해당 깊이의 값을 포함하지 않고 다음 깊이로 재귀

를 나누어 탐색하였다.

 

이 문제에서 조건은 total == S

 

구현 시 주의해야 할 점은 다음과 같았다.

• 원소가 하나인 경우도 경우의 수++ (ex. S = 0인 경우, {0}도 해당됨)
• 마지막 depth까지 가지 않았는데 total == S가 되더라도 경우의 수++하고, 마지막까지 가봐야 함 (또 다른 경우의 수가 생길 수 있음)

 

최종 코드

import java.util.Scanner;

public class Main {
    private static int N;
    private static int S;
    private static int count = 0;
    private static int[] arr;

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

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

        scanner.nextLine();
        String input = scanner.nextLine();

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input.split(" ")[i]);
        }

        for (int i = 0; i < N; i++) {
            backtracking(arr[i], i);
        }

        System.out.println(count);
    }

    private static void backtracking(int total, int depth) {
        if (depth == N - 1 && total == S) {
            count++;
        }

        depth++;
        if (depth < N) {
            backtracking(total + arr[depth], depth);
            backtracking(total, depth);
        }
    }
}