Depth-First

深さ優先探索（Depth-First Search） ある状態からはじめて、遷移できなくなるまで状態を進める。遷移できなくなったら1つ前の状態に戻る。上記はstackのpushとpopで実現できる。このため、深さ優先探索は再帰関数（呼び出し元に戻る）で実装できる場合が多い。 部分和問題（Partial Sum） {a1, a2, ..., an}からいくつか選んだ和がkになるかを判別する。今回は深さ優先探索で各組み合わせの和をすべて求める。a1から順に和に加えないor加えるを決める。このため、以下のような二分木に対して、深さ優先探索を行えば良い。 public class PartialSum…