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

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

1182번: 부분수열의 합

풀이

사용한 알고리즘 : 백트래킹

 

풀이전략

아래는 입력으로 {1,2,3}이 주어졌을 경우의 상태 트리이다.

루트 노드부터 설명하면, depth=1에서는 1이라는 원소가 삽입되는 경우 왼쪽 노드, 삽입되지 않는 경우

오른쪽 노드로 표시한다. 이와 같이 특정 원소가 삽입되는 경우는 왼쪽노드로, 삽입되지 않는 경우를 오른쪽 노드로 확장해나가면 위와같은 상태트리가 그려진다.

그리고 depth가 목표로 하는 깊이 n이 됐을 경우의 노드들을 보면

{1,2,3} 원소 집합에서 나올 수 있는 모든 부분집합을 구할 수 있다.(2^n개)

 

따라서 리프노드들에서 합이 S가 되는 노드의 개수를 구하면 정답이다.

(단, S=0인 경우 공집합도 계산하므로 구한 노드의 개수에서 1을 추가적으로 뺴줘야한다.)

 

제출코드

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

public class Main {

    static int N,S;
    static int count=0;
    static LinkedList<Integer> list;

    static void dfs(int depth,int val){
        if(depth==N){
            if(val==S){
                count++;
                return;
            }
        }
        else {
            dfs(depth + 1, val + list.get(depth));
            dfs(depth + 1, val);
        }
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        list = new LinkedList<>();

        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            list.add(Integer.parseInt(st.nextToken()));
        }

        dfs(0,0);
        if(S==0) System.out.println(count-1);
        else System.out.println(count);
    }
}