부분수열의 합

풀이

 dfs 완전 탐색 문제다. 아래와 같이 인덱스순으로 데이터를 포함할지에 따라 가지치기해서 쭉 내려간다. 마지막 층에서 합이 0을 만족하는지 검사하면 된다.

시간복잡도 : O(2^N)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.*;

public class Main {

    static int[] arr;

    static int result, S, N;

    public static void DFS(int index, int sum, int cnt){
        if(index>=N){
            if(cnt!=0 && sum==S)
                result++;
        }
        else {
            DFS(index + 1, sum + arr[index], cnt + 1);
            DFS(index + 1, sum, cnt);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        result = 0;
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        DFS(0,0, 0);

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

Python

N, S = map(int, input().split())
data = list(map(int, input().split()))
visited = [False] * N
result = 0

def dfs(index, sum, count):
    global result
    # 종료 조건
    if index >= N:
        if sum == S and count > 0:
            result += 1
        return
    # 하부함수 호출
    dfs(index+1, sum + data[index], count+1)
    dfs(index+1, sum, count)

dfs(0, 0, 0)
print(result)