Find the problem :
When used golang Brush once LeetCode On the subject ,78. A subset of , It is found that the data is always out of line , Print data found , There is data duplication
Error code :
var ans [][]int
func dfs(nums []int, nowNums []int, l, r int) {
ans = append(ans, nowNums)
if l == r {
return
}
for i := l; i < r; i++ {
dfs(nums, append(nowNums, nums[i]), i+1, r)
}
}
func subsets(nums []int) [][]int {
ans = [][]int{}
lenNums := len(nums)
dfs(nums, []int{}, 0, lenNums)
return ans
} Troubleshooting found that ,nowNums Slice in appen Into the ans after , It has changed , As a result, the original different data becomes the same
Problem analysis :
When dfs When the formal parameter of the
dfs(nums, append(nowNums, nums[i]), i+1, r)Equivalent to the following
x := append(nowNums, nums[i])
dfs(nums, x, i+1, r)
We all know , The slice will be automatically expanded , When the current capacity is insufficient , It will automatically expand the capacity according to the best situation ( It's not going to unfold here ), But you have to know something , Capacity expansion is to reapply a piece of memory , That is to say, the previous memory is not used , Take a look at this example
Code :
s1 := make([]int, 1, 1)
s1[0] = 10
s2 := s1
fmt.Printf("%p,%p\n", s1, s2)
fmt.Println(s1, s2)
s2 = append(s1, 10)
fmt.Printf("%p,%p\n", s1, s2)
fmt.Println(s1, s2) Output :
You can find ,s1 Array in s2 There is no change after modification , because s2 Reapplied for a piece of memory space , of no avail s1 Of , therefore s1 Unaffected
This ensures the operation of a slice , Is the other slice unaffected , What does it have to do with the problem , Even solved the problem !
however , This is in the case of capacity expansion , If there is no expansion ?
No expansion ,s2 The modification of will affect s1 The data of , This has led to a confusion in the data of the topic just now , The reason is that nowNums The slice is not expanded , Cause to have entered ans Slice data for , Changes will occur in subsequent recursions .
How to solve this problem , The best way is to directly extract the data of the current slice , Whether it will be changed later
Code :
var ans [][]int
func dfs(nums []int, nowNums []int, l, r int) {
nowNumsCopy := make([]int, len(nowNums))
copy(nowNumsCopy, nowNums) // direct copy Output the current slice data , Whether it is updated later or not
ans = append(ans, nowNumsCopy)
if l == r {
return
}
for i := l; i < r; i++ {
dfs(nums, append(nowNums, nums[i]), i+1, r)
}
}
func subsets(nums []int) [][]int {
ans = [][]int{}
lenNums := len(nums)
dfs(nums, []int{}, 0, lenNums)
return ans
}





