How can I create an array of 'n' positive integers where none of the subsequences of the a-CodePudding

I was watching a lecture on the question "subsequence sum equals to k" in which you're given an array of n positive integers and a target sum = k. Your task is to check if any of the subsequence of the array have a sum equal to the target sum. The recursive solution works in O(2^N). The lecturer said that if we memoize the recursive solution, the time complexity will drop to O(N*K). But as much as I understand, memoization simply removes overlapping subproblems. So if all of the subsequences have different sum, won't the time complexity of the solution still be O(2^N)? Just to test this hypothesis, I was trying to create an array of n positive integers where none of the subsequences have equal sum.

Also, I tried the tabulation method and was unable to understand why the time complexity drops in the case of tabulation. Please point to any resource where I can learn exactly what subproblems does tabulation avoid.

CodePudding user response：

If each value in the array is a different, positive power of the same base, no two sums will be equal.

Python code:

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)

CodePudding user response：

In the recursive case without memoization, you'll compute the sums for all subsequences, which has O(2^N) complexity.

Now consider the memoization case. Let dp[i][j] = 1 if there exists a subsequence in the array arr[i:] that has sum j, else dp[i][j] = 0.

The algorithm is

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]

For each index, we traverse the subsequence sums seen till yet (in range k), and mark them True for the current index. For each such sum, we also add the value of the current element, and mark that True.

Which sub-problems were reduced?

We just track if sum x is possible in a subarray. In the recursive case, there could be 100 subsequences that have sum x. Here, since we're using a bool to track if x is possible in the subarray, we effectively avoid going over all subsequences just to check if the sum is possible.

For each index, since we do a O(k) traversal of going through all sums, the complexity becomes O(N*k).