This one is a little tricky and certainly depends on how one interprets the question.
Write a golang function to find the unique combinations of a string.
I am taking the problem in a simple form. I will produce the combinations one would get assuming the string is left in order; that is to say that I am not considering combinations that would occur from any reordering of the characters from the original string.
func FindUniqueCombinations(str string) []string {
// Convert string to slice of runes
runes := []rune(str)
// Store unique combos
var combos []string
// Generate combos recursively
var searchForCombos func(start int, currentCombo[]rune)
searchForCombos = func(start int, currentCombo []rune) {
comboAsStr := string(currentCombo)
// Skip duplicates
if !slices.Contains(combos, comboAsStr) {
// Add current currentCombo to the result
combos = append(combos, string(currentCombo))
}
// Generate combos for remaining characters
for i := start; i < len(runes); i++ {
currentCombo = append(currentCombo, runes[i])
searchForCombos(i+1, currentCombo)
currentCombo = currentCombo[:len(currentCombo)-1]
}
}
searchForCombos(0, []rune{})
return combos
}
You can see that we've chosen a solution to uses recursion.
The approach is pretty simple. Given a string, start from the first character and generate the combinations that are possible by incrementing across the remaining characters making sure not to include any combinations that have already been generated.
How can we make it better? What would you change if you wanted to consider reordering characters to get all permutations?
Put your comments and suggestions below.
Top comments (0)