Problem statement

https://binarysearch.com/problems/Non-Adjacent-Combination-Sum/

Solution

Let dp[i] be all possible values we can get when we use the first i values. Then to evaluate dp[i] we need to look at

  1. dp[i-2] and add value A[i] to them.
  2. dp[i-1] fully.

Complexity

It is O(nk) for time and space. In fact space can be made O(k).

Code

class Solution:
    def solve(self, A, k):
        n = len(A)
        dp = defaultdict(set)
        dp[-1] = set([0])
        dp[0] = set([0, A[0]])
        if k in dp[0]: return True
        for i in range(1, n):
            dp[i] = dp[i-1].copy()
            for x in dp[i-2]: 
                if x + A[i] <= k: dp[i].add(x + A[i])
            if k in dp[i]: return True

        return False