Practice Algorithm Using Golang W/ Map Problem

Here is another one, the previous one is not solved, if you are interested on it, that’s will be a huge help!

I try to using different language to program in same problem:

Hope you understand Java

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        return helper(nums, target, 0, new HashMap<>());
    }
    
    private int helper(int[] nums, int target, int val, Map<Integer, Integer> m) {
        if (target == val) {
            return 1;
        }
        if (target < val) {
            return 0;
        }
        if (m.containsKey(val)) {
            return m.get(val);
        }
        int cnt = 0;
        for (int i = 0; i< nums.length; i++) {
            val += nums[i];
            cnt += helper(nums, target, val, m);
            val -= nums[i];
        }
        m.put(val, cnt);
        System.out.println(m);
        return cnt;
    }
}

Golang version:

func combinationSum4(nums []int, target int) int {
    return helper(nums, target, 0, make(map[int]int)) 
}

func helper(nums []int, target int, val int, m map[int]int) int {
    if target == val {
        return 1
    }
    if target < val {
        return 0
    }
    if val, ok := m[val]; ok {
        return m[val]
    }
    var cnt int
    for i:=0; i< len(nums);i++ {
        val += nums[i]
        cnt += helper(nums, target, val, m)
        val -= nums[i]
    }
    m[val] = cnt
    fmt.Println(m)
    return cnt
}

output from Java

{3=1}
{2=2, 3=1}
{1=4, 2=2, 3=1}
{0=7, 1=4, 2=2, 3=1}

output from Golang

map[3:1]
map[3:1 2:2]
map[3:1 2:2 1:3]
map[3:1 2:2 1:3 0:8]

You can see from result that getting worse at key 1, in Java it’s correct because (1, 1, 1, 1)(1, 1, 2) + (1, 2, 1)+ (1, 3)—> 2+1+1= 4. So all values in map sum up result in 7.
but somehow in golang, the value of key 1 is 3, and most weird thing is finally result is 8?
Does any big boss have some explanations on this funky result using same Algorithm between different language?
Thanks ahead!

Hey @Peng_Yan,

Your error is coming from this part:

if val, ok := m[val]; ok {
    return m[val]
}

Which should be this:

if v, found := m[val]; found {
    return v
}

Entire example: https://play.golang.org/p/S3SyA6Z6vR

All I did was port the Java example to Go so have a look and see if it works correctly for you.

Results:

map[3:1]
map[3:1 2:2]
map[3:1 2:2 1:4]
map[3:1 2:2 1:4 0:7]
7

Edit: Although the results seem weird so maybe the Java solution is incorrect? Or maybe I’m missing something here, but it is returning 7 which is correct.

1 Like

You are right, I made a stupid mistake.:joy: Thanks for help!

No worries :slight_smile:

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.