def backtrack(self, s, cur_lvl, ret):
        """
        Expand the search tree horizontally.
        i be the scanning index
        If s[:i] is palindrome, then palindrome partition the s[i:]

        :param s: the current temp string
        :param cur_lvl: the current temp result at current level
        :param ret: result
        :return:
        """
        if not s:
            ret.append(list(cur_lvl))

        for i in xrange(1, len(s)+1):
            if self.predicate(s[:i]):
                cur_lvl.append(s[:i])
                self.backtrack(s[i:], cur_lvl, ret)
                cur_lvl.pop()
dataset/ETHPy150Open algorhythms/LintCode/Palindrome Partitioning.py/Solution.backtrack/original