在Golang中使用回溯算法時，正確復制數組是一個重要的問題。回溯算法通常需要在遞歸過程中對數組進行修改，但有時我們需要保存原始數組的狀態以便回溯到上一步。在這種情況下，我們不能簡單地將原始數組直接賦值給一個新變量，因為它們共享同一塊內存空間，修改一個數組會影響到另一個數組。解決這個問題的方法是使用深拷貝，即創建一個新的數組并將原始數組的值依次復制到新數組中。在Golang中，可以使用copy()函數來完成這個操作，它會按字節級別復制數組的內容，確保新數組和原始數組完全獨立。通過正確復制數組，我們可以在回溯算法中安全地操作數組，而不會影響到原始數據的狀態。
問題內容
我有一個帶有值 [1, 2, 3] 的簡單數組，我想找到所有排列。我不明白為什么在循環中斷程序之前移動“復制”部分代碼。
func generatePermutations(curr, remains []int) [][]int {
if len(remains) == 0 {
return [][]int{curr}
}
var res [][]int
// DOESN'T WORK
c, r := make([]int, len(curr)), make([]int, len(remains))
copy(c, curr)
copy(r, remains)
for i := 0; i < len(remains); i++ {
// WORKS
//c, r := make([]int, len(curr)), make([]int, len(remains))
//copy(c, curr)
//copy(r, remains)
curr = append(curr, remains[i])
res = append(res, generatePermutations(curr, append(append(remains[:i]), remains[i+1:]...))...)
curr = c
remains = r
}
return res
}
登錄后復制
當復制位于循環之外時，結果如下：
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]
當復制位于循環內時，結果如下：
[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]
在第一個輸出中，有兩個帶有 [3,3,3] 的數組，這是錯誤的
解決方法
你說我既不修改“c”或“r”也不附加到它們，這部分是正確的。
在循環的第一次迭代中，
切片 c 和 curr 指向不同的支持數組，所以這很好。
但是當你這么做的時候
curr = c
登錄后復制
稍后，您實際上將兩個切片分配為指向同一個支持數組。
這意味著在第二次迭代中，您的 append 可以修改 curr 和 curr （“可以”，因為調整大小會更改 curr 的支持數組）。
這就是導致您在上面看到的奇怪行為的原因。
go 中的切片有點棘手，所以當你知道你會改變并傳遞它們時，最好避免分配，而是堅持完全復制它們（就像在“works”情況下所做的那樣）。
為了進一步閱讀，這是一個很好的資源：https://go.dev/blog/slices-簡介
