Arn*_*non 8 algorithm hashtable backtracking subset-sum
我已经被要求回答这个问题(这是技术上的功课).我考虑过哈希表,但我有点坚持我如何使这项工作的具体细节
这是问题:
鉴于ķ套整数阿1,阿2,..,甲ķ总尺寸O(的Ñ),则应该确定是否存在 一个1 ε 阿1,一个2 ε 阿2,..,一个ķ ε 甲ķ,使得一个1 + 一个2 + .. + 一ķ -1 = 一个ķ.您的算法应当T中运行ķ(Ñ)时间,其中T ķ(Ñ)= O(Ñ ķ/2 ×日志Ñ),用于甚至ķ,和O(Ñ (ķ +1)/ 2)为奇数值ķ.
任何人都可以给我一个大方向,以便我能够更接近解决这个问题吗？
小智 9
将k组分为两组.对于偶数k,两个组各有k/2组.对于奇数k,一组具有(k + 1)/ 2而另一组具有(k-1)/ 2组.计算每组中所有可能的总和(从每组中取一个元素).对于偶数k,您将获得两个数组,每个数组具有n k/2个元素.对于奇数k,一个阵列具有n (k + 1)/ 2,另一个阵列具有n (k-1)/ 2个元素.问题被简化为标准的"给定两个数组,检查是否可以通过从每个数组中取一个元素来达到指定的总和".