如何创建一个数组'n'数组的子序列和都不相等的正整数?

Question

我在看一个关于"子序列和等于k "这个问题的讲座给你一个n个正整数的数组，目标和为k。你的任务是检查该数组的子序列是否有一个和等于目标和的子序列。递归解在O(2^N)内有效。讲师说，如果我们记住递归解，时间复杂度将下降到O(N*K)。但据我所知，记忆只是消除了重叠的子问题。如果所有子序列的和不一样，解的时间复杂度不会还是O(2^N)吗?为了验证这个假设，我试图创建一个n个正整数的数组，其中每个子序列的和都不相等。

此外，我尝试了制表方法，但无法理解为什么在制表的情况下时间复杂度会下降。请指出任何资源，我可以确切地了解哪些子问题的制表避免。

Answer 1

注意，O(NK)并不总是小于O(2^N)。以K = 2^N为例，则O(KN) = O(N * 2^N)更大。

此外，这是当每个子序列和都不同时你要处理的范围。

如果N个整数是2的幂，例如:[2⁰， 2¹， 2²，…]，则每个子序列有一个不同的和，K=2^N是最小的非子序列和的正整数。

制表方法仅在已知K相对较小时是一种改进。

Answer 2

如果数组中的每个值都是相同基数的不同正幂，则没有两个和相等。

Python代码:

def f(A):
sums = set([0])
for a in A:
new_sums = set()
for s in sums:
new_sum = s + a
if new_sum in sums:
print(new_sum)
return None
new_sums.add(new_sum)
sums = sums.union(new_sums)
return sums
for b in range(2, 10):
A = []
for p in range(5):
A.append(b**p)
sums = f(A)
print(A)
print(len(sums))
print(sums)

Answer 3

在没有记忆的递归情况下，您将计算所有子序列的和，其复杂度为O(2^N)。

现在考虑记忆的情况。如果数组arr[i:]中存在子序列与j和，则设dp[i][j] = 1，否则设dp[i][j] = 0。

算法为

for each index i in range(n,0,-1):
j = array[i]
for each x in range(0,k):
dp[i][x] += dp[i+1][x]
if dp[i+1][x] == 1:
dp[i][x+j] = 1
return dp[0][k]

对于每个索引，我们遍历到目前为止看到的子序列和(在k范围内)，并将它们标记为当前索引的True。对于每个这样的和，我们还将当前元素的值相加，并将其标记为True。

哪些子问题减少了?

我们只是跟踪sumx在子数组中是否可行。在递归的情况下，可能有100个子序列的和为x。在这里，由于我们使用bool来跟踪x在子数组中是否可能，因此我们有效地避免了遍历所有子序列来检查求和是否可能。

对于每个索引，因为我们做了O(k)遍历所有的和，复杂度变成了O(N*k)。