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!