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

# 131. Palindrome Partitioning

## LeetCode [**131. Palindrome Partitioning**](https://leetcode-cn.com/problems/palindrome-partitioning/)\*\*\*\*

### Description

Given a string `s`, partition `s` such that every substring of the partition is a **palindrome**. Return all possible palindrome partitioning of `s`.

A **palindrome** string is a string that reads the same backward as forward.

**Example 1:**

```
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
```

**Example 2:**

```
Input: s = "a"
Output: [["a"]]
```

**Constraints:**

* `1 <= s.length <= 16`
* `s` contains only lowercase English letters.

### Tags

Backtracking

### Solution

Use the DFS template. Every time we examine the input string from the very first character to the whole string (Note: the index for traversal is from 1 to n, including n) if it is a palindrome. If it is, we append this substring to `path` , then DFS the remaining string. The boundary contiditon is the input string is empty, and we append `path` to the result 2D string slice.

### Complexity

* Time complexity: $$O(n\times2^n)$$, the worst case happens when the input string is the same character repeated n times. Thus it has $$2^n$$ possible partitioning of `s`.
* Space complexity: $$O(n^2)$$, needs $$O(n)$$ for path to store temporary result and stack space $$O(n)$$ for recursion.

### Code

```go
func partition(s string) [][]string {
	var ans [][]string
	dfs(&ans, s, []string{})
	return ans
}

func dfs(ans *[][]string, s string, path []string) {
	if len(s) == 0 {
		temp := make([]string, len(path))
		copy(temp, path)
		*ans = append(*ans, temp)
	}
	for i := 1; i <= len(s); i++ { // note: i is in [1,n]
		if isPalindrome(s[:i]) {
			path = append(path, s[:i])
			dfs(ans, s[i:], path)
			path = path[:len(path)-1]
		}
	}
}

func isPalindrome(s string) bool {
	for i := 0; i < len(s)/2; i++ {
		if s[i] != s[len(s)-i-1] {
			return false
		}
	}
	return true
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/131.-palindrome-partitioning.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.