Split a string so every piece reads the same forwards and back. At each position, try every prefix, keep only the palindromic ones, and recurse on the rest.
From index start, try each prefix s[start..end]. If it's a palindrome, commit that cut, add the piece to the path, and recurse from end+1. Undo the cut to try a longer prefix.
start == n → the whole string is partitionedbool isPal(string& s, int l, int r) {
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}
void dfs(int start, string& s,
vector<string>& path, vector<vector<string>>& out) {
if (start == s.size()) { // whole string consumed
out.push_back(path);
return;
}
for (int end = start; end < s.size(); end++) {
if (!isPal(s, start, end)) continue; // prune: not a palindrome
path.push_back(s.substr(start, end - start + 1)); // CHOOSE
dfs(end + 1, s, path, out); // EXPLORE remainder
path.pop_back(); // UNCHOOSE
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> out; vector<string> path;
dfs(0, s, path, out);
return out;
}Up to 2ⁿ⁻¹ ways to cut, each palindrome check O(n).
Recursion depth and the current partition path.
Only palindromic prefixes spawn a subtree, killing most branches.
isPal[i][j] DP table to make each check O(1) instead of O(n).