dfs

gistfile1.d

import std.stdio;
import std.range;
import std.algorithm;


void main()
{
  auto target = 13;
  auto ns = [1, 2, 4, 7];

  writeln(solve(target, ns));
}

int sum(int[] ns) {
  return reduce!("a + b")(0, ns);
}

int[] solve(int target, int[] ns)
{
  int[] f(int[] stock, int[] use)
  {
    if (stock.empty) {
      return (use.sum == target)? use : [];
    }

    int[] ret;

    // stockの先頭を使うパターン
    ret = f(stock[1..$], use ~ stock[0]);
    if (!ret.empty) return ret;

    // stockの先頭を使わないパターン
    ret = f(stock[1..$], use);
    if (!ret.empty) return ret;

    return [];
  }

  return f(ns, []);
}