时间戳

首页 > 解决方案 > Golang Slice - Java Arraylist - 递归回溯 - 经典算法 Powerset 在 Golang 中无法正常工作

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

问题描述

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

给定一组不同的整数 nums，返回所有可能的子集（幂集） 注意：解集不能包含重复的子集。示例：输入：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 中执行等效代码，则它不起作用。见下文： // nums :=[]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 切片引用被保持并且当回溯线

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

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

我真的在 GoLang 中努力实现这一目标。

标签： algorithmgorecursionslicebacktracking

解决方案

在这里切片内部

切片是数组段的描述符。它由指向数组的指针、段的长度及其容量（段的最大长度）组成。

您正在追加tmp然后result修改，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)
}

去游乐场的完整代码在这里

推荐阅读