给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回溯

• 时间复杂度O(n2^n)，空间复杂度O(n)
• Runtime: 429 ms, faster than 24.28%
• Memory Usage: 81.8 MB, less than 15.30%

首先用DFS，然后回溯。

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
  let result = [];
  dfs(0, result, [], s);
  return result;
};

var dfs = function(start, result, curr, s) {
  if (start >= s.length) {
    result.push(curr);
  }
  
  for (let i = start; i < s.length; i++) {
    if (isPalindrom(s, start, i)) {
      curr.push(s.substring(start, i + 1));
      dfs(i + 1, result, curr.slice(), s);
      curr.pop();
    }
  }
}

var isPalindrom = function(s, left, right) {
  while(left < right) {
    if (s[left++] !== s[right--]) {
      return false;
    }
  }
  return true;
}