Golang Slice-Java Arraylist-递归回溯-经典Algo Powerset在Golang中不能正常工作

Question

[
  [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);
     }

}

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[0:len(tmp)-1]

Answer 1

所以，正如你提到的，问题是你使用slice的方式。Slice的大小为3个字（对于64位计算机，1个字=8字节（64位））。

第一个字指向片的第一个元素，第二个字存储片的长度，第三个字存储片的容量。您可以在这里阅读更多关于slice的内容（一篇初学者友好的文章）。

因此，正如您已经知道的，您是在对tmp中的值追加引用，而不是对TEMP中的值的副本追加引用。

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