DEV Community

J Fowler
J Fowler

Posted on • Updated on

Unique combinations of a string

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 and empty string
        if !slices.Contains(combos, comboAsStr) && len(comboAsStr) > 0 {
            // 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
}
Enter fullscreen mode Exit fullscreen mode

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.

Thanks!

The code for this post and all posts in this series can be found here

Top comments (0)