[アルゴリズム]伯俊>#1182.部分数列の和

質問リンク

白俊#1182。部分数列の和

解答方法

枝切りができない完全なナビゲーションの問題!Nの最大値は20なので、完全に探知して問題を解決できるでしょう~?dfsを用いてすべてのケースを検索した.sumという部分数列の合計値が渡されるたびに、sum=sが満たされるとカウントされます.

コード#コード#

import java.util.*;
public class BOJ1182 {

    private static int n;
    private static int s;

    private static int[] array;

    private static int count = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        s = sc.nextInt();

        array = new int[n];
        for (int i = 0; i < n; i++) array[i] = sc.nextInt();

        dfs(0, 0);

        System.out.print(count);
    }

    private static void dfs(int index, int sum) {
        if ((index != 0) && (sum == s)) count++;

        for (int i = index; i < n; i++) {
            sum += array[i];
            dfs(i + 1, sum);
            sum -= array[i];
        }
    }
}