algorithm - 给定N个数组，每个数组有几种方法贡献一个元素并加到k？

Question

假设我有N个数组。这N个数组在数组A的数组中。有多少个N元组使得对于元组t，

sum = 0
for i = 0 ... N-1
    sum += A[i][t[i]]
sum == k

解决这个问题的有效方法是什么我能想到的最好的办法就是列举所有的可能性。
这不是家庭作业问题。我在leetcode上看到了 this，我很好奇这个普通病例的解决方案。

Answer 1

概念解决方案（可以改进）：
对每个数组中的元素排序
将每个数组中的元素移动所有数组的绝对最小值（abs_min-要移动所有数组，您将从所有数组的每个元素中减去abs_min）-您现在拥有所有具有非负元素的数组，并且正在搜索target_sum = initial_sum - num_arrays*abs_min
将您的curr_array设置为第一个
二进制搜索target_sum在curr_array中的位置。您需要考虑curr_array中的所有元素，并在此位置下使用索引取一个这样的元素，从target_sum中减去它，然后递归地对下一个数组重复搜索。
我相信（AdRosid）复杂度将是某处O(num_arrays*N*log(N))，其中N是数组中元素的最大数目。
改进机会：
我觉得把所有数组的移位abs_min是不必要的（只是一种帮助思考的技巧）也许在第4步递归深入一步之前，target_sum可能会被当前数组的min移位？
重新排序数组，以便首先考虑较短的数组，这可能会提高性能（要考虑的递归上层中较低的元素数）[编辑]，或者可能会按数组的最小值的降序重新排序（以最积极的方式从target_sum中取出）？
采用消除/复用初始数组中的重复项的方案可能有助于-即索引键=唯一值的映射和索引集的映射值）。如果不需要特定的元组，那么一个唯一值->出现次数的映射就足够了（这可能是有用的，如果可以确保重复存在-例如数组中的值在严格范围内，数组是相当长的鸽洞原则）。
[在{{1, 2, 3}, {42,43, 44, 45, 46, 47}}]
上限=元素的索引严格大于提供的值如果您希望值小于或等于，请取严格低于该索引的值！啊！
零基索引约定
49第一个数组中的目标和得到index=3的上限（因此需要考虑3以下的所有索引）
第一个数组-开始索引=2/value=3在第一个数组中，您将在第二个数组中查找target_sum的46第二个二进制搜索的上限是index=5（并且将严格地往下看），所以从index=4/value=46开始（算法会去掉47的值）。46是很好的并且保留了下来，index=3/value=45是不够的，而且（没有一个3-rd数组递归到其中）算法甚至不会考虑在index=3/value=45下。
第一个数组，index=1/value=2，在第二个数组中查找47的目标和获取上限（二进制搜索）提供index=7（在其下严格搜索）因此index=6/value=4747被保留，46和更低，并且算法被切断
在第一个数组中，index=0/value=1，在第二个数组中查找48的目标和。上限再次是7，在index=6/value=47我们得到一个不足的值并终止。
所以，总的来说：
二进制搜索总数：第一个数组中为1，第二个数组中为3。
测试的成功均衡器总数=2（找到两个元组）。
测试的总未成功等式=3（直到第二个数组不再提供满意的答案）。
执行的加/减总计=3（第一个数组中的每个值一个）
相比之下，彻底扫描将得到：
没有二进制搜索
加总=3*6=18
测试的总成功等式=2
总的未成功相等测试=16