package main

func partition(s string) [][]string {
	length := len(s)
	lists := [][]string{}
	list := []string{}
	partitionHelper(&lists, &list, s, 0, length)
	return lists
}

// Backtracking algorithm, try to understand & remember
func partitionHelper(lists *[][]string, list *[]string, s string, beg, end int) {
	if beg == end {
		newList := make([]string, len(*list))
		copy(newList, *list)
		*lists = append(*lists, newList)
		return
	}
	for i := beg + 1; i <= end; i++ {
		if isPalindrome(s, beg, i) {
			*list = append(*list, s[beg:i])
			partitionHelper(lists, list, s, i, end)
			*list = (*list)[:len(*list)-1] // Backtrack
		}
	}
}

func isPalindrome(s string, beg, end int) bool {
	for ; beg < end-1; beg, end = beg+1, end-1 {
		if s[beg] != s[end-1] {
			return false
		}
	}
	return true
}

// func main() {
// 	fmt.Println(partition("aabbb"))
// }