> For the complete documentation index, see [llms.txt](https://anand-aryan.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://anand-aryan.gitbook.io/leetcode/131.-palindrome-partitioning.md).

# 131. Palindrome Partitioning

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",

Return

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

## Solution <a href="#solution" id="solution"></a>

```java
public class Solution {

   public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        solve(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void solve(String s, int pos, List<String> current, List<List<String>> result) {
        if (pos == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int start = pos + 1; start <= s.length(); start++) {
            if (isPalindrome(s, pos, start - 1)) {
                current.add(s.substring(pos, start));
                solve(s, start, current, result);
                current.remove(current.size() - 1);
            }
        }

    }

    private boolean isPalindrome(String s, int start, int end) {
        if (start == end) {
            return true;
        }

        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }

            start++;
            end--;
        }

        return true;
    }
}
```