Создание комбинации Голанга сделало ошибку

Question

Я имею дело с проблемой программирования

Учитывая два целых числа n и k, вернуть все возможные комбинации чисел k из 1 ... n.

и с входом n = 5, k = 4, выход должен быть [[1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5]], вот мое решение для Голанга

func combine(n int, k int) [][]int {
    result := [][]int{}
    comb := []int{}
    subcom(0, k, n, &comb, &result)
    return result
}

func subcom(s, k, n int, comb *[]int, result *[][]int) {
    if k > 0 {
        for i := s + 1; i <= n-k+1; i++ {
            c := append(*comb, i)
            subcom(i, k-1, n, &c, result)
        }
    } else {
        *result = append(*result, *comb)
    }
}

Я думаю, что мое решение верное, но оно возвращается [[1 2 3 5][1 2 3 5] [1 2 4 5] [1 3 4 5] [2 3 4 5]].

После отладки я обнаружил, что [1 2 3 4] был добавлен к результирующему фрагменту в начале, но позже изменился на [1 2 3 5], что привело к повторению двух [1 2 3 5]s.Но я не могу понять, что здесь не так.

Answer 1

Это распространенная ошибка при использовании append.

Когда ваш код запускает c:=append(*comb,i), он сначала пытается использовать выделенную память в базовом массиве, чтобы добавить новый элемент и только создать новыйнарезать, когда это не удалось сделать.Это то, что меняет [1 2 3 4] на [1 2 3 5] - потому что они совместно используют одну и ту же базовую память.

Чтобы исправить это, скопируйте, когда вы хотите добавить в результат:

now := make([]int,len(*comb))
copy(now,*comb)
*result = append(*result,now)

Илииспользуйте ярлык копирования:

*result = append(*result, append([]int{},*comb...))

Обновление:

Чтобы понять, что я имею в виду под базовой памятью, необходимо понять внутреннюю модель среза Go.

В Goсрез имеет структуру данных под названием SliceHeader, которая доступна через пакет reflect и является той, на которую ссылаются, когда вы используете unsafe.Sizeof и берете адрес.

SliceHeader заботится о трех элементах: Len, Cap и Ptr.Первые два тривиальны: они - то, для чего len() и cap().Последним является uintptr, который указывает на память данных, содержащихся в срезе.

Когда вы копируете срез по горизонтали, создается новый SliceHeader, но с тем же содержимым, включая Ptr.Таким образом, основная память не копируется, а разделяется.