백준 1182번 : 부분수열의 합 java

이 문제는 dfs를 이용한 백트래킹 문제입니다.

dfs를 이용하여 입력받은 수열을 순회하면서 지금까지 입력받은 부분수열의 합이 S와 같아지면 경우의 수를 추가하면 됩니다.

코드를 보며 추가로 설명드리겠습니다.

---

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

public class Main {
    static int N, S;
    static int[] numArr;
    static boolean[] visited;
    static int count = 0;

    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());

        numArr = new int[N];
        visited = new boolean[N];

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

        dfs();

        System.out.println(count);
    }

    static void dfs(){
        for(int i = 0; i<N; i++){
            visited[i] = true;
            dfs(numArr[i], 1, i);
            visited[i] = false;
        }
    }

    static void dfs(int sum, int cnt, int exIdx){
        if(sum == S)
            count++;

        if(cnt == N)
            return;

        for(int i = exIdx+1; i<N; i++){
            if(visited[i])
                continue;

            visited[i] = true;
            dfs(sum + numArr[i], cnt+1, i);
            visited[i] = false;
        }
    }
}

이 문제를 풀 때 유의해야 하는 점은 -7 -3 -2 이런 순서로 입력을 받든 -3 -7 -2와 같은 순서로 입력을 받든지 같은 부분수열이라는 것입니다.

따라서 exIdx를 이용하여 이전에 탐색했던 부분수열들은 다시 탐색하지 않도록 했습니다.