1 files changed, 35 insertions, 0 deletions
diff --git a/src/dfs.c b/src/dfs.c
new file mode 100644
index 0000000..3f34001
--- /dev/null
+++ b/src/dfs.c
@@ -0,0 +1,35 @@
+#include <stdlib.h>
+#include "dfs.h"
+#include "structs.h"
+#include "common.h"
+
+struct front_item * rec(struct data * d, int i, struct item * it) {
+  if(i == d->N) {
+    return new_front_item(it->p, it->w, NULL, NULL);
+  }
+
+  // Go left (select item)
+  it->p += d->items[i].p;
+  it->w += d->items[i].w;
+  struct front_item * f1 = rec(d, i+1, it);
+  it->p -= d->items[i].p;
+  it->w -= d->items[i].w;
+  // Go right (do not select item)
+  struct front_item * f2 = rec(d, i+1, it);
+
+  // Merge
+  struct front_item * f1_end = f1;
+  for(;f1_end->next!=NULL; f1_end = f1_end->next);
+  f1_end->next = f2;
+  f2->prev = f1_end;
+  
+  return f1;
+}
+
+struct front_item * dfs(struct data * d) {
+  struct item * it = (struct item *)malloc(sizeof(struct item));
+  it->p = 0;
+  it->w = 0;
+
+  return rec(d, 0, it);
+}