**Problem Statement:**

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

**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.

**Solution:**

**Algorithm:**

- Use DFS to traverse all the possible partitions.
- Use a helper function to check if the current substring is a palindrome.
- If the current substring is a palindrome, add it to the path and continue to traverse the rest of the string.
- If the current substring is not a palindrome, do not add it to the path and continue to traverse the rest of the string.
- If the current index is equal to the length of the string, add the current path to the result.
- After the traversal is completed, return the result.

**Code:**

```
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> path = new ArrayList<>();
dfs(s, 0, path, res);
return res;
}
private void dfs(String s, int index, List<String> path, List<List<String>> res) {
if (index == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
path.add(s.substring(index, i + 1));
dfs(s, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
```

**Time Complexity:**

O(n*2^n)O(nā2n) The time complexity of the backtracking algorithm is exponential, because in the worst case, we need to add n-1 separators into a string of length n, which results in 2^n2

**Space Complexity:**

O(n)O(n) The space complexity of the backtracking algorithm is linear, because in the worst case, the depth of the recursion tree can reach nn.

## Top comments (0)