Golang Slice - Java Arraylist - Recursion Backtracking - Classi c Al go Powerset не работает должным образом в Golang

Question

Я пытаюсь решить проблему набора мощности с помощью рекурсии и обратного отслеживания в Golang:

Учитывая набор различных целых чисел, nums, вернуть все возможные подмножества (набор мощности) Примечание. Набор решений не должен содержат повторяющиеся подмножества. Пример: Ввод: nums = [1,2,3] Вывод:

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

Это классическая проблема c, решаемая с помощью рекурсии и отслеживания с возвратом с использованием кода 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.

Answer 1

Итак, как вы упомянули, проблема в том, как вы используете slice. Срез имеет размер 3 слова (1 слово = 8 байт (64-бит) для 64-битной машины).

1-е слово указывает на первый элемент среза, 2-е слово хранит длину среза а третье слово хранит емкость среза. Вы можете узнать больше о срезе здесь (статья для новичков).

Итак, как вы уже знаете, вы добавляете ссылку на значения в tmp, а не на копию значений в temp.

Решение вашей проблемы простое: создайте копию tmp и добавьте эту копию в свой результат.

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

Итак, теперь на значение в результате не повлияет, если вы меняете tmp slice

Answer 2

Внутреннее устройство среза в здесь

Срез - это дескриптор сегмента массива. Он состоит из указателя на массив, длины сегмента и его емкости (максимальной длины сегмента).

Вы добавляете tmp в result, а затем изменяете tmp означает, что последние измененные данные tmp из l oop будут сохранены в 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 игровая площадка здесь