Palindrome Partitioning

Backtracking with palindrome checks on each cut

Backtrack on where to cut. Precompute palindrome checks with DP.

Published Apr 16, 2026

Problem

Given a string s, return every way to partition s such that every substring in the partition is a palindrome.

Input

s = "aab"

Output

[["a","a","b"], ["aa","b"]]

Input

s = "a"

Output

[["a"]]

Intuition

At any position i, the partition has two decisions: how long is the next piece, and is that piece a palindrome.

The backtracking template handles both: walk i from 0, try each possible end j ∈ [i, n), check whether s[i..j+1] is a palindrome, and if so, push it on the path and recurse from j + 1. Emit the path when i == n.

There are at most 2^(n-1) ways to partition a length-n string (one binary choice per gap). Each piece costs O(n) to palindrome-check and to copy into the output — giving O(n · 2ⁿ) in the worst case (e.g. all same character).

The palindrome check is the tuning knob: you can precompute an n × n table in O(n²) time and O(1) per query, or check on the fly in O(len) per cut. For moderate n the on-the-fly check is simpler and plenty fast.

Approach

Backtracking with on-the-fly palindrome check

TimeO(n · 2ⁿ)

SpaceO(n)

Recommended

Small and clean. At each start, iterate end from start to n-1, check if s[start..=end] is a palindrome, and if yes recurse from end + 1.

impl Solution {
    pub fn partition(s: String) -> Vec<Vec<String>> {
        let b = s.as_bytes();
        let n = b.len();
        let mut out = Vec::new();
        let mut path: Vec<String> = Vec::new();
        fn is_palin(b: &[u8], lo: usize, hi: usize) -> bool {
            let (mut l, mut r) = (lo, hi);
            while l < r {
                if b[l] = b[r] {
                    return false;
                }
                l = 1;
                r -= 1;
            }
            true
        }
        fn dfs(
            start: usize,
            b: &[u8],
            s: &str,
            n: usize,
            path: &mut Vec<String>,
            out: &mut Vec<Vec<String>>,
        ) {
            if start == n {
                out.push(path.clone());
                return;
            }
            for end in start..n {
                if is_palin(b, start, end) {
                    path.push(s[start..=end].to_string());
                    dfs(end + 1, b, s, n, path, out);
                    path.pop();
                }
            }
        }
        dfs(0, b, &s, n, &mut path, &mut out);
        out
    }
}

Rust · runnable

function partition(s: string): string[][] {
  const out: string[][] = [];
  const path: string[] = [];
  const n = s.length;
  const isPalin = (lo: number, hi: number): boolean => {
    while (lo < hi) {
      if (s[lo] !== s[hi]) return false;
      lo++;
      hi--;
    }
    return true;
  };
  const dfs = (start: number): void => {
    if (start === n) {
      out.push(path.slice());
      return;
    }
    for (let end = start; end < n; end++) {
      if (isPalin(start, end)) {
        path.push(s.slice(start, end + 1));
        dfs(end + 1);
        path.pop();
      }
    }
  };
  dfs(0);
  return out;
}

TypeScript · runnable

Backtracking with precomputed DP palindrome table

TimeO(n · 2ⁿ)

SpaceO(n²)

Build an n × n boolean table in O(n²): isP[i][j] = (s[i] == s[j]) && (j - i < 2 || isP[i+1][j-1]). Then the palindrome check during DFS is O(1).

Wins when there are many recursive subtrees that all touch the same (i, j) substrings. For highly-repetitive strings (like "aaaa…"), this is a measurable speedup. For random strings, it's usually a wash.

impl Solution {
    pub fn partition(s: String) -> Vec<Vec<String>> {
        let b = s.as_bytes();
        let n = b.len();
        let mut is_p = vec![vec![false; n]; n];
        for i in (0..n).rev() {
            for j in i..n {
                if b[i] == b[j] && (j - i < 2 || is_p[i + 1][j - 1]) {
                    is_p[i][j]= true;
                }
            }
        }
        let mut out= Vec::new();
        let mut path: Vec<String> = Vec::new();
        fn dfs(
            start: usize,
            s: &str,
            n: usize,
            is_p: &[Vec<bool>],
            path: &mut Vec<String>,
            out: &mut Vec<Vec<String>>,
        ) {
            if start == n {
                out.push(path.clone());
                return;
            }
            for end in start..n {
                if is_p[start][end] {
                    path.push(s[start..=end].to_string());
                    dfs(end + 1, s, n, is_p, path, out);
                    path.pop();
                }
            }
        }
        dfs(0, &s, n, &is_p, &mut path, &mut out);
        out
    }
}

Rust · runnable

function partition(s: string): string[][] {
  const n = s.length;
  const isP: boolean[][] = Array.from({ length: n }, () =>
    new Array(n).fill(false)
  );
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (s[i] === s[j] && (j - i < 2 || isP[i + 1][j - 1])) {
        isP[i][j] = true;
      }
    }
  }
  const out: string[][] = [];
  const path: string[] = [];
  const dfs = (start: number): void => {
    if (start === n) {
      out.push(path.slice());
      return;
    }
    for (let end = start; end < n; end++) {
      if (isP[start][end]) {
        path.push(s.slice(start, end + 1));
        dfs(end + 1);
        path.pop();
      }
    }
  };
  dfs(0);
  return out;
}

TypeScript · runnable

Trace

Partitioning "aab":

step	start	path	considered	action
1	0	[]	s[0..0] = a	palindrome, recurse
2	1	[a]	s[1..1] = a	palindrome, recurse
3	2	[a,a]	s[2..2] = b	palindrome, recurse
4	3	[a,a,b]	-	emit
5	1	[a]	s[1..2] = ab	not palindrome, skip
6	0	[]	s[0..1] = aa	palindrome, recurse
7	2	[aa]	s[2..2] = b	palindrome, recurse
8	3	[aa,b]	-	emit
9	0	[]	s[0..2] = aab	not palindrome, skip

Two partitions emitted.

Edge cases

Empty string — one partition, the empty list.
Single character — one partition, [[c]].
All same characters ("aaaa") — exponentially many partitions (2ⁿ⁻¹). The DP approach's O(1) palindrome check is noticeably faster here.

Takeaway

Partitioning problems are combination-sum in disguise. The path elements are substrings rather than numbers, the "valid choice" check is palindrome-ness rather than sum, and the start pointer moves forward by the chosen piece's length. Same skeleton, different decorations.

Medium#78

Subsets

The canonical backtracking template. Include or exclude each element.

Medium#46

Permutations

Backtracking with a ‘used’ set. Draw the decision tree.

Medium#39

Combination Sum

Unbounded choices. How do you avoid duplicates?