Two code with exactly same logic gives different solutions.
Is there a bug within Go, or did I make some stupid mistake in my code?
This is a leetcode question LeetCode - Permutations II.
The C++ code below is an ACCEPTED solution written by someone.
C++ Code
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int>>res;
helper(num, 0, num.size(), res);
return res;
}
void helper(vector<int> num, int start, int j, vector<vector<int> > &res) {
if (start == j-1) {
res.push_back(num);
return;
}
for (int i = start; i < j; i++) {
if (start == i || num[start] != num[i]) {
swap(num[start], num[i]);
helper(num, start + 1, j, res);
}
}
}
};
int main() {
Solution s;
vector<int> nums({2,1,2});
vector<vector<int>> res = s.permuteUnique(nums);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << " " << res[i][j];
}
cout << endl;
}
}
I translated the C++ code above to the golang code below:
Golang Code
package main
func permuteUnique(nums []int) [][]int {
qsort(nums, 0, len(nums)-1)
res := make([][]int, 0, len(nums))
helper(&res, nums, 0)
return res
}
func helper(res *[][]int, nums []int, start int) {
if start == len(nums)-1 {
copied := make([]int, len(nums))
copy(copied, nums)
*res = append(*res, copied)
return
}
for i := start; i < len(nums); i++ {
if start == i || nums[start] != nums[i] {
nums[i], nums[start] = nums[start], nums[i]
helper(res, nums, start+1)
}
}
}
func main() {
nums := []int{2,1,2}
res := permuteUnique(nums)
for i := 0; i < len(res); i++ {
for j := 0; j < len(res[0]); j++ {
print(" ", res[i][j]);
}
println()
}
}
func qsort(nums []int, low, high int) {
if low >= high {
return
}
i, j, pivot := low, high, nums[low]
for i < j {
for i < j && nums[j] >= pivot {
j--
}
nums[i] = nums[j]
for i < j && nums[i] <= pivot {
i++
}
nums[j] = nums[i]
}
nums[i] = pivot
qsort(nums, low, i-1)
qsort(nums, i+1, high)
}
Output
Both of code above is able to run instantly. Below is my output:
fondoger@localhost:Desktop$ g++ test.cpp -o app && ./app
1 2 2
2 1 2
2 2 1
fondoger@localhost:Desktop$ go run test.go
1 2 2
2 1 2
2 2 1
1 2 2
I tried debugging using Goland IDE and Clion IDE for several hours, but I can't find out the truth.