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

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

1182번: 부분수열의 합

 

<문제해석>

1. 종료조건은 tree level이 N까지 진행될 때이다.

2. 합이 S가 되면 count +1을 한다.

  - 합이 S가 되더라도 탐색은 계속 진행한다.

3. 모든 탐색이 끝나면 count를 출력한다.

4. 부분집합을 구하는 것이기 때문에 지금 수(A[i])를 더하거나 더하지 않는 수, 2가지 경우의 수로 나뉜다.

  - 현재 수(A[level])를 더하고 다음 level로 넘어간다.

  - 현재 수를 더하지 않고 다음 level로 넘어간다.

5. 이런 식으로 모든 경우의 수를 탐색해서 트리를 확장한다.

 

※ 백트래킹 : 현재 상태에서 선택 가능한 모든 후보군을 따라 들어가며 탐색해보는 알고리즘

 

<코드구현 #1>

import java.util.Scanner;
import java.util.Arrays;
import java.lang.StringBuilder;
import java.util.HashSet;

public class Main {
    static int N, S;
    static int sum = 0, count = 0;
    static int A[];
    //static int Ans[];
    static boolean visited[];
    static StringBuilder sb = new StringBuilder();


    void inputData(){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        A = new int[N];
        //Ans = new int[M];
        visited = new boolean[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }
        sc.close();
    }

    void DFS(int sum, int level) {
        // 종료 조건
        // tree level이 N만큼 진행되면 종료
        if (level == N) {
            // 부분수열의 합이 S와 같으면 count++
            if (sum == S) count++;
            return;
        }
        // 재귀호출 조건
        // tree에서 진행 될 때 두가지 경우의 수로 나뉜다.
        // 1-1. 현재 수(A[level])를 더한다.
        DFS(sum + A[level], level+1);
        // 1-2. 현재 수를 더하지 않는다.
        DFS(sum, level+1);
    }
    
    void Solve() {
        //Arrays.sort(A);
        DFS(0, 0);
        // S가 0이면 공집합의 경우가 같이 카운트가 되기 때문에 1을 빼줘야 한다.
        if (S == 0) count = count-1;
        System.out.println(count);
    }
 
    public static void main(String[] args) {
        Main m = new Main();
        m.inputData(); // 입력함수
        m.Solve();
    }
}