[BOJ] 1182. 부분수열의 합

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

접근 방법

처음에 코드를 순차적으로 합이 되는 경우만 생각을 해보았다.

하지만

예제에 { 2 0 } { 0 , 0 } 이라면 답은 3이 된다는 사실을 알게 되어

백트래킹을 사용해서 코드를 다시 짜게 되었다.

주의 사항

Need Know

1. BackTracking

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int S;
    static int[] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        br.close();
        bw.flush();
        bw.close();
    }

    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void solve() throws IOException {
        for(int i=0; i<N; i++){
            backtracking(arr[i], i);
        }

        bw.write(count+"");
    }
    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);
        }
    }
}