部分和問題 | Codetter（こーどったー）

/**
 * ある数列の中から、幾つかのの項を選んで所望の合計になるかどうか判定する。
 * @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]);
		}

	}
}