question example:
given a string "aaaabbbasd" and dictionary, for example {a, aa, aaa, b, bb, s, d}
1) find one possible way to split the string into words from dictionary
2) find all possible ways to split the string into words from dictionary

Searching for the best approach on web I found different ones: dp, backtracking + memorization, dfs + memorization.
I lost in all of this huge variety.
Does somebody knows what approach is the best here?