Please read this before solving


Recursive/backtracking solution is accepted. not sure why it is put in dp.
output should be sorted.


Because before directly going to call backtrack function, you must make sure is it breakable or not?
Well InterviewBit test cases consider, that the given string is breakable but in leetcode, there are some cases when above is not true, the latter is more general. So you must check is it breakable or not.
Hence it should be in dp.