Golang 切片 - Java Arraylist - 递归回溯 - 经典算法 Powerset 在 Golang 中无法正常工作

Question

我正在尝试在 Golang 中使用递归和回溯来解决幂集问题：

给定一组不同的整数，nums，return所有可能的子集（幂集）注意：解决方案集不得包含重复的子集。例子：输入：nums = [1,2,3] 输出：

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

这是使用下面的 Java 代码通过递归和回溯解决的经典问题：

public List<List<Integer>> subsets(int[] nums) {
       List<List<Integer>> list = new ArrayList<>();
       backtrack(list, new ArrayList<>(), nums, 0);
     return list;

}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
     }

}

但是，如果我在 Golang 中执行等效代码，则它不起作用。见下文： // 数字 :=[]int{1,2,3}

func powerSubSets(nums []int){
   result :=[][]int{}
   tmp:=[]int{}
   powerSubsetsDFS(nums,tmp, 0, result)
   fmt.Println("Final Result ",result)

}

func powerSubsetsDFS(nums []int, tmp []int, idx int, result [][]int) {
   result = append(result,tmp)
   fmt.Println("result idx ",idx,result)
   for i:=idx;i<len(nums);i++{
     tmp = append(tmp,nums[i])
     powerSubsetsDFS(nums,tmp,idx+1,result)
     fmt.Println(" subract ", idx , tmp)
     tmp = tmp[0:len(tmp)-1]
     fmt.Println(" subract after  ", idx , tmp)
}

}

如果您看到输出打印：

    result idx  0 [[]]
result idx  1 [[] [1]]
result idx  2 [[] [1] [1 2]]
result idx  3 [[] [1] [1 2] [1 2 3]]
 subract  2 [1 2 3]
 subract after   2 [1 2]
 subract  1 [1 2]
 subract after   1 [1]

问题是 tmp slice 引用被保留并且当回溯线

 tmp = tmp[0:len(tmp)-1]

被执行，它引用了它最近在结果中添加的同一个 tmp 切片。理想情况下，不应触摸结果切片。但看起来由于 slice 引用了相同的 tmp，最终它将把答案留给 []。

为了实现这一点，我真的在 GoLang 中苦苦挣扎。

Answer 1

here

中的切片内部

A slice is a descriptor of an array segment. It consists of a pointer to the array, the length of the segment, and its capacity (the maximum length of the segment).

您在 result 中追加 tmp，然后修改 tmp，这意味着循环中 tmp 的最后修改数据将存储在 result 中.

在 tmp 中追加时存储在一个新变量中并传递它。现在您不需要在附加后删除，因为您使用的是新变量。并在递归调用时使用i+1。

func powerSubsetsDFS(nums []int, tmp []int, idx int, result [][]int) [][]int {
   result = append(result,tmp)
   for i:=idx;i<len(nums);i++{
     tmp2 := append(tmp, nums[i]) // store in a new variable
     result = powerSubsetsDFS(nums,tmp2,i+1,result)
   }
   return result;
}

func powerSubSets(nums []int){
   result :=[][]int{}
   tmp:=[]int{}
   result = powerSubsetsDFS(nums,tmp, 0, result)
   fmt.Println("Final Result ",result)
}

go playground 中的完整代码here

Answer 2

因此，正如您提到的，问题在于您使用 slice 的方式。切片的大小为 3 个字（对于 64 位机器，1 个字= 8 字节（64 位））。

第一个字指向切片的第一个元素，第二个字存储切片的长度，第三个字存储切片的容量。您可以阅读有关切片的更多信息 here（适合初学者的文章）。

正如您已经知道的那样，您正在附加对 tmp 中值的引用，而不是对 temp 中值的副本。

您的问题的解决方案很简单，创建一个 tmp 副本并将该副本添加到您的结果切片中。

tmpcpy := make([]int, len(tmp))
copy(tmpcpy, tmp)
result = append(result,tmpcpy)

所以现在，如果您更改 tmp 切片，结果中的值将不会受到影响

Golang 切片 - Java Arraylist - 递归回溯 - 经典算法 Powerset 在 Golang 中无法正常工作

Golang Slice - Java Arraylist - Recursion Backtracking - Classic Algo Powerset not working as desired in Golang

algorithm

recursion

backtracking

go

slice