Given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?
For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete. A variant of this problem could be formulated as –
Given a value n cents and m type of coins with values { c1, c2, .. , cm} cents each. How many ways can we make the n cents by using the coins as many times as you want?
For example, for n = 5 and C = {1, 2, 5}, there are 4 solutions {{1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}}.
Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive.
For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4].