Гоша прибыл к подножью самого опасного вулкана, проголодался и замечтался. Вот примерный ход его мыслей: "Эх, вот бы можно было питаться словами вместо еды! Берём, к примеру, слово "картошка", бросаем его в кастрюлю с солёным кипятком, варим и помешиваем. Сколько, интересно, слов получится, если перемешать все буквы в "картошке"?" Напишите функцию Permutations(input string) []string, которая принимает строку и выводит все перестановки её символов в алфавитном порядке. Примечания Например, если передать функции Permutations(input string) []string строку "abc" или "cab", то она должна вернуть [abc acb bac bca cab cba]. Для сортировки объектов используйте пакет sort.

package main

import ( "fmt" "sort" )

func Permutations(input string) []string { var result []string var backtrack func(start int, str []rune)

backtrack = func(start int, str []rune) {
	if start == len(str) {
		result = append(result, string(str))
		return
	}

	for i := start; i < len(str); i++ {
		str[start], str[i] = str[i], str[start]
		backtrack(start+1, str)
		str[start], str[i] = str[i], str[start]
	}
}

str := []rune(input)
backtrack(0, str)
sort.Strings(result)

return result

}

func main() { input := "abc" output := Permutations(input) fmt.Println(output) }