深さ優先探索で部分和問題を解きます
深さ優先探索で部分和問題を解きます
/*** ある数列の中から、幾つかのの項を選んで所望の合計になるかどうか判定する。* @author tatesuke*/public class 部分和問題 {public static void main(String[] args) {int[] 数列 = {1, 4, 3, 2, 5};int 合計 = 13;System.out.println(new 部分和Solver(数列, 合計).solve());}private static class 部分和Solver {final int[] 数列;final int 合計;部分和Solver(int[] 数列, int 合計) {this.数列 = 数列;this.合計 = 合計;}boolean solve() {return solve(0, 0);}private boolean solve(int i, int sum) {if (sum == 合計) {return true;}if (i == 数列.length) {return false;}if (solve(i + 1, sum)) {return true;}return solve(i + 1, sum + 数列[i]);}}}