> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/4.depth-first-search/136.palindrome-partitioning.md).

# 136.Palindrome Partitioning

## 1.Description(Medium)

Given a string*s*, partition\_s\_such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

**Example**

Given s =`"aab"`, return:

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

## 2.Code

遇到要求所有组合、可能、排列等解集的题目，一般都是用DFS + backtracking来做。这种需要输出所有结果的基本上都是DFS的解法

<https://soulmachine.gitbooks.io/algorithm-essentials/content/java/dfs/palindrome-partitioning.html>

```
//时间复杂度O(2^n)，空间复杂度O(n)
public List<List<String>> partition(String s) {
        List<List<String>>  result=new ArrayList<>();
        ArrayList<String> path=new ArrayList<String>();
        dfs(s,0,path,result);
        return result;        
        }

    public boolean isPalindrome(String s,int start,int end){
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public void dfs(String s,int start,ArrayList<String> path,List<List<String>> result){
        if(start==s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }
        for(int i=start;i<s.length();i++){
            if(isPalindrome(s,start,i)){
                path.add(s.substring(start, i+1));
                dfs(s,i+1,path,result);
                path.remove(path.size()-1);
            }
        }
    }
```

Palindrome Partition II is Dynamic Programming