How you should do this depends on a number of important things: how many numbers will you have and how large will they be? In addition, as I understand it, your data can change (add / remove numbers, etc.), right ?. How often do you need to do these queries?
I will introduce two solutions. I suggest you use the second, as I suspect that this is better for what you need, and it is much easier to understand.
Solution 1 - Dynamic Programming
Let S[i] = true if we can make sum i and false otherwise.
S[0] = true
To get the actual numbers that make up your sum, you must save another vector P[i] = the last number that was used to make sum i . You would update this according to the if condition above.
The complexity of this time is O(numberOfNumbers * maxSumOfAllNumbers) , which is pretty bad, especially since you have to re-run this algorithm whenever your data changes. It also slows down even for one run, while your numbers can be very large, and there can be many. In fact, "a lot" is misleading. If you have 100 numbers, and each number can be up to 10,000, you will do approximately 100 * 10,000 = 1,000,000 operations each time your data changes.
This is a good decision to know, but not very useful in practice, or at least not in your case, I think.
It is a bit of C # for the approach I suggest:
class Program { static void Main(string[] args) { List<int> testList = new List<int>(); for (int i = 0; i < 1000; ++i) { testList.Add(1); } Console.WriteLine(SubsetSum.Find(testList, 1000)); foreach (int index in SubsetSum.GetLastResult(1000)) { Console.WriteLine(index); } } } static class SubsetSum { private static Dictionary<int, bool> memo; private static Dictionary<int, KeyValuePair<int, int>> prev; static SubsetSum() { memo = new Dictionary<int, bool>(); prev = new Dictionary<int, KeyValuePair<int, int>>(); } public static bool Find(List<int> inputArray, int sum) { memo.Clear(); prev.Clear(); memo[0] = true; prev[0] = new KeyValuePair<int,int>(-1, 0); for (int i = 0; i < inputArray.Count; ++i) { int num = inputArray[i]; for (int s = sum; s >= num; --s) { if (memo.ContainsKey(s - num) && memo[s - num] == true) { memo[s] = true; if (!prev.ContainsKey(s)) { prev[s] = new KeyValuePair<int,int>(i, num); } } } } return memo.ContainsKey(sum) && memo[sum]; } public static IEnumerable<int> GetLastResult(int sum) { while (prev[sum].Key != -1) { yield return prev[sum].Key; sum -= prev[sum].Value; } } }
Perhaps you need to do some error checking and possibly keep the last amount in the class so that you cannot call GetLastResult with a different amount than the last amount with the Find number. Anyway, this is an idea.
Solution 2 - a randomized algorithm
Now it’s easier. Save the two lists: usedNums and unusedNums . Also save the usedSum variable, which at any time contains the sum of all numbers in the usedNums list.
Whenever you need to insert a number into your set, add it to one of the two lists (it doesn’t matter, but do it randomly so that there is a relatively uniform distribution). Update usedSum accordingly.
Whenever you need to remove a number from your set, find out which of the two lists it is in. You can do this with a linear search if you have little (this time, it means more than 10,000, maybe even 100,000 on a fast computer and assuming that you do not perform this operation often and quickly. In any case, linear Search can be optimized if you need it.). After you find the number, remove it from the list. Update usedSum accordingly.
Whenever you need to find if there are numbers in your set that sum with S , use this algorithm:
while S != usedSum if S > usedSum // our current usedSum is too small move a random number from unusedNums to usedNums and update usedSum else // our current usedSum is too big move a random number from usedNums to unusedNums and update usedSum
At the end of the algorithm, the list usedNums will give you numbers whose sum is S
This algorithm should be good for what you need, I think. It handles changes to the data set very well and works well for a large number of counters. It also does not depend on how large the numbers are, which is very useful if you have large numbers.
Please write if you have any questions.