브루트포스. 부분 수열의 합

문제

N개의 정수 입력 받음. 크기가 양수이고, 부분 수열의 원소의 합의 경우의 수를 구하는 문제.

해결방향성

N개의 부분수열을 구하는 문제이므로 백트래킹을 사용한다.

코드

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

public class Main {
    static int N, M;
    static int[] array;
    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());
        M = Integer.parseInt(st.nextToken());
        array = new int[N];

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


        DFS(0, 0);

        if (M == 0) {
            // 공집합 포함 : XXXXX
            answer -= 1; // 공집합은 카운트에서 빼줘야한다.
        }
        bw.write(String.valueOf(answer));

        bw.flush();
        br.close();
        bw.close();
    }
    static int answer = 0;
    private static void DFS(int depth, int sum) {
        if (depth == N) { // N개의 depth 에 도달하면
            if (sum == M) { // 문제에서 요구하는 합과 일치하면
                answer++; // 카운트 증가
            }
            return;
        }
        DFS(depth + 1, sum + array[depth]); //  O : 재귀문으로 합하는 경우
        DFS(depth + 1, sum); // X : 재귀문으로 합하지않는 경우
    }
}

결론

• 백트래킹을 통해 경우의 수를 찾는 문제. visited배열을 구현하지 않는 방식에서 신선했음.
• 1 2 3 4 5, 1 2 3 4, 1 2 3 5 , 1 2 3, 1 2 4 5, 1 2 4, 방식으로,
  o o o o o, o o o o x, o o o x o, o o o x x, ... 이런 방식으로 x x x x x 까지 카운트.
• 단, x x x x x 인 경우는 합에 포함되지않아야한다. (요구하는 합이 0일때, 카운트되므로 뺀다.)