Efficiently finding duplicates in lists of numbers

Question

I decided to try my hand at solving the knapsack problem.

My idea involved generating $i$ tables, where $i: 1 \le i \lt n$, and each cell of an $i$ table contains one of the possible sums of the objects to fit into the knapsack. The $i$ tables will then be sorted. Then for each of the $k$ numbers to be tested, I'll run a binary search on the sorted arrays.

I realised that there may be sums which repeat. I feel like recording them will be unnecessary waste of space.

So I want to determine if for any new number $k$ to be added to the list, if $k$ is a duplicate of any number in the list. It is trivial to just search the list, but this is too inefficient, and takes $O(n^2)$ operations, making the trade off with space complexity a bad deal.

I wanted a linear time algorithm for solving this problem. I thought of a function, which takes in inputs, and the function is such that if any new input is the same as a previous input, the function will provide a certain known output. This function should work in constant time or at worst, logarithmic time.

I have tried several means of constructing the function but they failed.

Answer 1

Use any efficient set data structure, based e.g. on hashtables or balanced search trees.

Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will come up with.

That said, you may want to check out pseudo-polynomial algorithms for Knapsack, and problem variants that have polynomial-time algorithms.