Palindrome Partitioning: Backtracking + DP Pre-check

def partition(s):
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = (s[i] == s[j]) and (j - i <= 2 or is_pal[i+1][j-1])

    result = []
    def bt(start, current):
        if start == n:
            result.append(current[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                current.append(s[start:end+1])
                bt(end + 1, current)
                current.pop()
    bt(0, [])
    return result

print(partition("aab"))  # [['a','a','b'], ['aa','b']]

# Minimum cuts for palindrome partition (DP)
def minCut(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n-1,-1,-1):
        for j in range(i,n):
            is_pal[i][j] = (s[i]==s[j]) and (j-i<=2 or is_pal[i+1][j-1])
    dp = list(range(n))  # dp[i] = min cuts for s[0..i]
    for i in range(1, n):
        if is_pal[0][i]: dp[i] = 0; continue
        for j in range(1, i+1):
            if is_pal[j][i]:
                dp[i] = min(dp[i], dp[j-1] + 1)
    return dp[n-1]

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> partition(string s) {
    int n = s.size();
    vector<vector<bool>> isPal(n, vector<bool>(n, false));
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            isPal[i][j] = (s[i]==s[j]) && (j-i<=2 || isPal[i+1][j-1]);

    vector<vector<string>> result;
    vector<string> current;
    function<void(int)> bt = [&](int start) {
        if (start == n) { result.push_back(current); return; }
        for (int end = start; end < n; end++) {
            if (isPal[start][end]) {
                current.push_back(s.substr(start, end-start+1));
                bt(end + 1);
                current.pop_back();
            }
        }
    };
    bt(0);
    return result;
}

import java.util.*;

public class PalindromePartition {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for (int i = n-1; i >= 0; i--)
            for (int j = i; j < n; j++)
                isPal[i][j] = s.charAt(i)==s.charAt(j) && (j-i<=2 || isPal[i+1][j-1]);

        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, isPal, new ArrayList<>(), result);
        return result;
    }

    void backtrack(String s, int start, boolean[][] isPal, List<String> curr, List<List<String>> result) {
        if (start == s.length()) { result.add(new ArrayList<>(curr)); return; }
        for (int end = start; end < s.length(); end++) {
            if (isPal[start][end]) {
                curr.add(s.substring(start, end+1));
                backtrack(s, end+1, isPal, curr, result);
                curr.remove(curr.size()-1);
            }
        }
    }
}