I can't understand why DFS would work here, would someone please explain it ?
I would like to see the brute force solution, so that I can learn from it.
I haven't figured this out yet, but I think one brute force solution is to generate all permutations of the + and - signs, and that will require 2^n permutations.
For example, for a list with 3 numbers, you have 2^3 possible options. And then you loop through each one to see if it produces the target sum. Each option is just the binary representation of that number, from 0 to 2^n
0 --- 1 --+ 2 -+- 3 -++ 4 +-- 5 +-+ 6 ++- 7 +++