1

This is an interview question. I'm given an array of numbers (duplicates, negative numbers possible) and the lower and upper limit of a range. I need to find the number of subsets possible which will sum to a number within the range. I did look at the question which looks for a particular sum (find all subsets that sum to a particular value) but I don't think trying to do that for every number in the range is the most efficient thing to do.

Range can be from -10^7 to 10^7.

Community
  • 1
  • 1
Bharg
  • 311
  • 1
  • 2
  • 15
  • It seems like the answer you link to can be adapted. You've probably already given it a little thought, but you don't describe where you got stuck in your question, so it's hard to provide useful help other than just writing a solution. – Paul Hankin Dec 27 '16 at 14:48
  • It is clearly NP-hard. A dynamic programming approach is natural. – John Coleman Dec 27 '16 at 15:07
  • This problem is at least as hard as subset sum problem, but when the sum of weights is bounded I don't know if it remains np-hard or becomes tractable. – Saeed Amiri Dec 27 '16 at 17:12

1 Answers1

1

The classic DP for subset sum can be modified to solve this problem, keeping a count instead of a boolean indicator for whether a solution with the given sum exists.

def subset_sum_count(lst, a, b):
    sum_count = collections.Counter({0: 1})
    for x in lst:
        for s, c in list(sum_count.items()):
            sum_count[s + x] += c
    return sum(c for (s, c) in sum_counts.items() if a <= s <= b)
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120