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

문제 링크 : https://www.acmicpc.net/problem/1182

이 문제는 백트래킹을 통해 풀 수 있습니다. bfs나 dfs로 풀기에는 경우의 수가 더 많기 때문에 백트래킹으로 풀어 모든 경우를 체크하고, 중복으로 셀 수 있는 부분을 조절하기 위해 인덱스를 설정하여 현재 시점의 인덱스 이후의 값만 조회하여 더하는 작업을 진행하면 되겠습니다.

다음은 코드입니다.

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

public class Main{
    static int N,S;
    static int[] req = new int[21];
    static int res = 0;
    static boolean[] check = new boolean[21];

    static void backtracking(int num, int cnt, int idx){
        if(cnt>N) return;

        if(num == S) res++;

        for(int i=idx;i<N;i++){
            if(!check[i]){
                check[i] = true;
                // 백트래킹 진행 시 현재 인덱스를 기억해서 인덱스 이후의 값만 참조
                // 따라서 중복으로 카운트 되는 것을 방지
                backtracking(num+req[i],cnt+1, i+1);
                check[i] = false;
            }
        }
    }

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

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

        backtracking(0,0,0);
        if(S==0) res--;
        System.out.println(res);
    }
}