Log inSign up
hardGeeksforGeeksNot Started

Print All Palindromic Partitions

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a string s, find and return all possible palindromic partitions of the given string.

A palindromic partitioning is a grouping of substrings such that every individual segment is a palindrome.

Example 1:

Input: s = "geeks"
Output: [["g", "e", "e", "k", "s"], ["g", "ee", "k", "s"]]
Explanation: The substrings "g", "e", "k", "s", and "ee" are all valid palindromes.

Example 2:

Input: s = "nitin"
Output: [["n", "i", "t", "i", "n"], ["n", "iti", "n"], ["nitin"]]
Explanation: All three decompositions contain strictly palindromic segments.

Constraints:

  • 1 <= s.length <= 16
  • s consists of lowercase English letters only

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the pattern of precomputing predicate matrices (like palindrome tables) to accelerate backtracking recursions.
  • Formulate tree visualizations for string partition problems.
  • Analyze time and space bounds for backtracking algorithms returning power sets of cuts.

1. Bitmask All Partitions + Post Validation

Intuition

For every mask from 0 to 2^(N-1) - 1, if bit i is set, place a partition after character i. Check whether every substring in the generated partition is palindromic.

Algorithm

  1. Step 1: Generate all 2^(N-1) possible string partitions.
  2. Step 2: For each partition, verify if every substring component is a valid palindrome.
  3. Step 3: If all parts are palindromes, add the partition list to result.
  4. Step 4: Return result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 bool isPalin(const std::string& s) {
8 int l = 0, r = (int)s.size() - 1;
9 while (l < r) {
10 if (s[l++] != s[r--]) return false;
11 }
12 return true;
13 }
14
15 std::vector<std::vector<std::string>> allPalindromicPerms(std::string s) {
16 int n = s.length();
17 std::vector<std::vector<std::string>> result;
18 int total = 1 << (n - 1);
19
20 for (int mask = 0; mask < total; mask++) {
21 std::vector<std::string> current;
22 int last = 0;
23 bool valid = true;
24 for (int i = 0; i < n - 1; i++) {
25 if ((mask >> i) & 1) {
26 std::string sub = s.substr(last, i - last + 1);
27 if (!isPalin(sub)) { valid = false; break; }
28 current.push_back(sub);
29 last = i + 1;
30 }
31 }
32 if (valid) {
33 std::string sub = s.substr(last);
34 if (isPalin(sub)) {
35 current.push_back(sub);
36 result.push_back(current);
37 }
38 }
39 }
40 return result;
41 }
42};
43
44int main() {
45 Solution solver;
46 std::vector<std::vector<std::string>> res = solver.allPalindromicPerms("geeks");
47 std::cout << "Bitmask Partitions for 'geeks':\n";
48 for (const auto& p : res) {
49 std::cout << "[ ";
50 for (const auto& w : p) std::cout << "\"" << w << "\" ";
51 std::cout << "]\n";
52 }
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(2^N * N) — 2^(N-1) masks iterated, each taking O(N) time to split and validate.
  • Space complexity: O(2^N * N) — Stores all partitions in memory.

2. Backtracking with Two-Pointer Palindrome Check

Intuition

From index start, test every end up to N-1. If s[start..end] is a palindrome, append it to path, recurse on end+1, and backtrack.

When to apply: Standard backtracking with on-the-fly palindrome verification.

Algorithm

  1. Step 1: Define backtrack(start, current) from start index 0.
  2. Step 2: If start == s.length, push a copy of current to result and return.
  3. Step 3: Loop end from start to s.length - 1.
  4. Step 4: Check if substring s[start..end] is a palindrome using two pointers in O(length).
  5. Step 5: If palindrome, push s[start..end] to current, recurse on backtrack(end + 1), and pop.
  6. Step 6: If not palindrome, skip without recursing.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 bool isPalindrome(const std::string& s, int l, int r) {
8 while (l < r) {
9 if (s[l++] != s[r--]) return false;
10 }
11 return true;
12 }
13
14 void backtrack(const std::string& s, int start, std::vector<std::string>& path, std::vector<std::vector<std::string>>& result) {
15 if (start == (int)s.length()) {
16 result.push_back(path);
17 return;
18 }
19 for (int end = start; end < (int)s.length(); end++) {
20 if (isPalindrome(s, start, end)) {
21 path.push_back(s.substr(start, end - start + 1));
22 backtrack(s, end + 1, path, result);
23 path.pop_back();
24 }
25 }
26 }
27
28 std::vector<std::vector<std::string>> allPalindromicPerms(std::string s) {
29 std::vector<std::vector<std::string>> result;
30 std::vector<std::string> path;
31 backtrack(s, 0, path, result);
32 return result;
33 }
34};
35
36int main() {
37 Solution solver;
38 std::vector<std::vector<std::string>> res = solver.allPalindromicPerms("geeks");
39 std::cout << "Backtracking Output for 'geeks':\n";
40 for (const auto& p : res) {
41 std::cout << "[ ";
42 for (const auto& w : p) std::cout << "\"" << w << "\" ";
43 std::cout << "]\n";
44 }
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Explores palindrome cuts with O(N) verification per cut.
  • Space complexity: O(N) — O(N) recursion call stack and path array.

3. Backtracking with 2D DP Table Precomputation

Intuition

Fill table dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1]). The backtracking function queries dp[start][end] instantly in O(1) time without rescanning characters.

When to apply: Optimal standard: O(1) palindrome checks via dynamic programming precomputation.

Algorithm

  1. Step 1: Precompute a 2D boolean DP table isPalin[i][j] in O(N2) where isPalin[i][j] = (s[i] == s[j] && (j - i <= 2 || isPalin[i+1][j-1])).
  2. Step 2: In backtrack(start), check if start == s.length; if so, record current partition.
  3. Step 3: Loop end from start to s.length - 1.
  4. Step 4: In O(1), check isPalin[start][end]. If true, push s[start..end], recurse on backtrack(end + 1), and backtrack by popping.
  5. Step 5: Return result containing all valid palindromic decompositions.

Palindromic Partitioning Decision Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at index 0 of string 'aab' with current partition []
Visual state
Values and pointers at this exact step
tree
Start
s = 'aab', []

Node order shown; add connections to display explicit tree edges.

Variables at this step
start
0
current
[]
Check / comparison
start = 0, remaining string = 'aab'
Decision / next transition
Explore candidate prefixes starting from index 0
Why this step matters

Start at index 0 of string aab with current partition [].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 void backtrack(const std::string& s, int start, const std::vector<std::vector<bool>>& dp, std::vector<std::string>& path, std::vector<std::vector<std::string>>& result) {
8 if (start == (int)s.length()) {
9 result.push_back(path);
10 return;
11 }
12 for (int end = start; end < (int)s.length(); end++) {
13 if (dp[start][end]) {
14 path.push_back(s.substr(start, end - start + 1));
15 backtrack(s, end + 1, dp, path, result);
16 path.pop_back();
17 }
18 }
19 }
20
21 std::vector<std::vector<std::string>> allPalindromicPerms(std::string s) {
22 int n = s.length();
23 std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
24
25 for (int i = n - 1; i >= 0; i--) {
26 for (int j = i; j < n; j++) {
27 if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
28 dp[i][j] = true;
29 }
30 }
31 }
32
33 std::vector<std::vector<std::string>> result;
34 std::vector<std::string> path;
35 backtrack(s, 0, dp, path, result);
36 return result;
37 }
38};
39
40int main() {
41 Solution solver;
42 std::vector<std::vector<std::string>> res = solver.allPalindromicPerms("geeks");
43 std::cout << "Optimal DP Output for 'geeks':\n";
44 for (const auto& p : res) {
45 std::cout << "[ ";
46 for (const auto& w : p) std::cout << "\"" << w << "\" ";
47 std::cout << "]\n";
48 }
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(N^2 + 2^N) — O(N2) bottom-up table initialization plus O(2N) backtracking decomposition.
  • Space complexity: O(N^2) — O(N2) memory for the 2D boolean DP lookup table.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Bitmask All Partitions + Post ValidateO(2^N * N)O(2^N * N)Generates massive non-palindromic partitions before checking them.
2.Backtracking with Two-Pointer Palindrome CheckO(2^N * N)O(N)Re-evaluates palindrome status for identical substrings across different branches.
3.Backtracking with 2D DP Table Precomputation (Optimal)OptimalO(N^2 + 2^N)O(N^2)Uses O(N2) memory for lookup table.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Filling the DP table in the wrong loop direction, causing uninitialized dp[i+1][j-1] lookups. Loop i downwards from n-1 to 0 and j upwards from i to n-1 to guarantee inner subproblems are already solved.

Pitfall 2:

Forgetting to pop from path when backtracking. Always pair path.push_back() / path.add() before the recursive call with path.pop_back() / path.remove() immediately after.

Crucial Edge Cases to Validate:

  • Single character string (e.g. a) -> returns [[a]].
  • All identical characters (e.g. aaa) -> returns all 2^(3-1) = 4 partitions.
  • No multi-character palindromes (e.g. abc) -> returns strictly [[a, b, c]].
  • Even length palindrome (e.g. abba) -> correctly includes both [a, b, b, a], [a, bb, a], and [abba].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether the output requires all partitions or only the minimum cut count (which would be the O(N2) DP Palindrome Partitioning II problem).
  2. Explain the bottom-up table direction clearly: decreasing i ensures dp[i+1][...] is populated.
  3. Highlight how pruning non-palindromic prefixes early prevents deep invalid recursive tree traversal.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the worst-case number of palindromic partitions for a string of length N?

Back to DSA Sheet