Возможные комбинации m out n, отсортированные и без повторения

Я написал следующую функцию, чтобы получить все возможные комбинации m из n, отсортированные и без повторения. Я новичок в Go, и мне интересно, какие улучшения я могу сделать с точки зрения производительности и передовых методов.

Ввод: m и массив строк

Вывод: массив всех возможных комбинаций, объединенных в строки

package main
import (
    "fmt"
    "sort"
    "strings"
)

func main() {

    var m int64 = 3
    items := []string{"b", "a", "d", "e", "f", "c", "k", "h"}
    result := FindPossibleCombination(m, items)

    fmt.Println( result )
    fmt.Println( len(result) )
}


func FindPossibleCombination(m int64, items []string) []string {
    sort.Strings(items)

    return rec(m, items, 0)
}

func rec(m int64, items []string, start int) []string {
    var res []string
    n := len(items)

    // edge cases
    if 
    int64(n) < m || 
    (m == 0 || n == 0) || 
    start < 0 ||
    m < 0 {
        return res
    }
    
    // Base case, recursion stops here
    if int64(n) == m {
        comb := strings.Join(items,"")
        return []string{comb}
    }
    
    for i := start; i < n; i++ {
        // copy items so I don't tamper with the original array
        tempArr := make([]string, len(items), cap(items))
        copy(tempArr, items)
        
        if  i == 0 {
            // i = 0: remove last item
            tempArr = tempArr[:n-1]
        } else {
            // i > 0: remove item at len(items) - i
            // when i increases move left to remove another item
            // until we arrive to m items and recursion stops
            copy(tempArr[n-1-i:], tempArr[n-i:])
            tempArr[n-1] = ""
            tempArr = tempArr[:len(tempArr)-1]
        }
            
            // call function again with new array and new start.
            // By specifying new start i, we freeze all items to the right of the 
            // removed item to make sure no combination is repeated.
            res = append(res, rec(m, tempArr, i)...)
    }
    return res
}

Попробуйте на детской площадке:
https://play.golang.org/p/hJN8gatqzud

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *