> For the complete documentation index, see [llms.txt](https://emmaguo100.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://emmaguo100.gitbook.io/leetcode/02-15-2022-131.md).

# 02/15/2022 131

Method:

1. Iteratively generate all possible substrings beginning start index. The end index increments from start till the end of the string.
2. For each of the substring generated, check if it is a palindrome.
3. If the substring is a palindrome, the substring is a potential candidate. Add substring to the path list and perform a depth-first search on the remaining substring. If current substring ends at index end, <mark style="color:purple;">**end+1**</mark> becomes the start index for the next recursive call.
4. Backtrack if start index is greater than or equal to the string length and add the path list to the result.

* Time Complexity : O(N⋅2^N), where N is the length of string s. This is the worst-case time complexity when all the possible substrings are palindrome. For each substring, it takes O(N) time to generate substring and determine if it is a palindrome or not.
* Space: O(N) This space will be used to store the recursion stack.

class Solution { List\<List> result = new ArrayList<>(); LinkedList path = new LinkedList<>();

```
public List<List<String>> partition(String s) {
    if(s == null || s.length() == 0) return result;
    backtracking(s, 0);
    return result;   
}

private void backtracking(String s, int startIndex){
    //base condition
    if(startIndex >= s.length()){
        result.add(new ArrayList<>(path));
        return;
    }
    
    for(int end = startIndex; end < s.length(); end++){
        if(isPalindrome(s, startIndex, end)){
            String str = s.substring(startIndex, end + 1); 
            path.add(str);
            backtracking(s, end + 1);//notice it is end + 1
            path.removeLast();
        }
    }
    
}
private boolean isPalindrome(String s, int start, int end){
    while(start < end){
        if(s.charAt(start) != s.charAt(end)) return false;
        start++;
        end--;
    }
    return true;
}
```

}