CODEWITHSUNDEEP
algorithmgorecursionslicebacktracking
Learner
Learner

Reputation: 65

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

I am trying to solve powerset problem using Recursion and backtracking in Golang:

Given a set of distinct integers, nums, return all possible subsets (the power set) Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output:

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

This is a classic problem solved by Recursion and Backtracking using the Java code below :

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

}

However, if I do the equivalent code in Golang it does not work. See below : // 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)
}

}

If you see the output prints:

    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]

The issue is that the tmp slice reference is being hold and when the backtracking line 

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

is executed, it refers the same tmp slice that it has recently added in result. Ideally the result slice should not be touched. But looks like due to slice refrencing the same tmp is acted upon and ultimately it will leave the answer to [].

I am really struggling in GoLang to achieve this.

Upvotes: 1

Views: 920

Answers (2)

Eklavya
Eklavya

Reputation: 18480

Slice internals in 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).

You are appending tmp in result and then modify the tmp that's means last modified data of tmp from the loop will stored in result.

Store in a new variable when appending in tmp and pass it. Now you don't need to remove after appending since you are using a new variable. And use i+1 when call recursively.

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

Full code in go playground here

Upvotes: 0

Omkar Rokade
Omkar Rokade

Reputation: 120

So, as you mentioned the problem is the way you are using slice. Slice has a size of 3 words( 1 word= 8byte(64-bit) for 64-bit machine).

The 1st word points to the first element of the slice, the 2nd word stores length of the slice and the 3rd word stores the capacity of the slice. You can read more about slice here (a beginner friendly article).

So as you already know you are appending reference to the values in the tmp and not the copy of values in temp.

The solution to your problem is simple, create a copy of tmp and add that copy to your result slice.

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

So now the value in the result won't be affected if you alter tmp slice

Upvotes: 0

Related Questions