部分和問題

深さ優先探索で部分和問題を解きます

深さ優先探索で部分和問題を解きます

  • タグ:
  • タグはありません
/**
*
* @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]);
}
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX