package Backtrack
func partition(s string) [][]string {
result := make([][]string, 0)
path := make([]string, 0)
var f func(int)
f = func(index int) {
if index == len(s) {
tmp := make([]string, len(path))
copy(tmp, path)
result = append(result, tmp)
return
}
for end := index + 1; end <= len(s); end++ {
if isPalindrome(s[index:end]) {
path = append(path, s[index:end])
f(end)
path = path[:len(path)-1]
}
}
}
f(0)
return result
}
func isPalindrome(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}