Hi All,
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 +++