How to correctly copy an array when using backtracking algorithm in Golang?

Copying the array correctly is an important issue when using the backtracking algorithm in Golang. Backtracking algorithms usually require modifications to the array during the recursive process, but sometimes we need to save the state of the original array in order to backtrack to the previous step. In this case, we cannot simply assign the original array directly to a new variable because they share the same memory space and modifying one array will affect the other array. The solution to this problem is to use a deep copy, which creates a new array and copies the values ​​of the original array into the new array one after another. In Golang, this operation can be accomplished using the copy() function, which copies the contents of the array at the byte level to ensure that the new array is completely independent of the original array. By correctly copying the array, we can safely manipulate the array in the backtracking algorithm without affecting the state of the original data.

Question content

I have a simple array with values ​​[1, 2, 3] and I want to find all permutations. I don't understand why the "copy" part of the code is moved before the loop breaks the program.

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
}

When the copy is outside the loop, the results are as follows: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 3 3] [3 3 3]]

When the copy is inside the loop, the result is as follows: [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

In the first output, there are two arrays with [3,3,3], which is wrong

Solution

You saidI both Not modifying "c" or "r" nor appending to them, this part is correct.

In the first iteration of the loop, Slices c and curr point to different backing arrays, so that's fine.

But when you do that

curr = c

Later, you actually assign both slices to point to the same backing array.

This means that on the second iteration, your append can be modified curr and curr ("can" because resizing changes curr's supporting array).

This is what causes the strange behavior you see above.

Slices in go are a bit tricky, so when you know you'll be changing and passing them around, it's best to avoid allocations and instead stick to copying them exactly (as you do in the "works" case).

For further reading, here is a great resource: https://go.dev/blog/slices-introduction

The above is the detailed content of How to correctly copy an array when using backtracking algorithm in Golang?. For more information, please follow other related articles on the PHP Chinese website!