Hi all
i come across a weird thing of golang multi-level slices when dealing with leetcode
my basic algorithm should be correct
but some weird things happen when i’m using multi-level slices
i know this code can be tedious and boring
so i add lots of comments and really hope to get your help!!!
big thanks in advance
package main
import "fmt"
func main() {
// use nums to generate all avilable subsets
// e.g. nums = [3, 5]
// subsets = [[], [3], [5], [3,5]]
nums := []int{9, 0, 3, 5, 7}
fmt.Println(subsets(nums))
}
// this algorithms should be correct:
// we use dynamic programming and add current iterating num to
// previous existing subsets
func subsets(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
// use dynamic programming
dp := make([][][]int, len(nums))
dp[0] = [][]int{nil, {nums[0]}}
// dp iteration
for i := 1; i < len(dp); i++ {
dp[i] = dp[i-1]
for _, v := range dp[i-1] {
dp[i] = append(dp[i], append(v, nums[i]))
}
}
// return final result
return dp[len(dp)-1]
// However, ans is not correct
}
// correct output should be:
// [[],[9],[0],[9,0],[3],[9,3],[0,3],[9,0,3],[5],[9,5],[0,5],[9,0,5],[3,5],
// [9,3,5],[0,3,5],**[9,0,3,5]**,[7],[9,7],[0,7],[9,0,7],[3,7],[9,3,7],
// [0,3,7],[9,0,3,7],[5,7],[9,5,7],[0,5,7],[9,0,5,7],[3,5,7],[9,3,5,7],[0,3,5,7],**[9,0,3,5,7]**]
// my answer is(note the ** different):
// [[],[9],[0],[9,0],[3],[9,3],[0,3],[9,0,3],[5],[9,5],[0,5],[9,0,5],[3,5],
// [9,3,5],[0,3,5],**[9,0,3,7]**,[7],[9,7],[0,7],[9,0,7],[3,7],[9,3,7],
// [0,3,7],[9,0,3,7],[5,7],[9,5,7],[0,5,7],[9,0,5,7],[3,5,7],[9,3,5,7],[0,3,5,7],**[9,0,3,7,7]**]
// this is weird
// actually, the value of [9,0,3,5] is first generated correctly by my code
// but it's rewritten when generating [9,0,3,7] in iteration of appending 7 to existing result