Find every possible pair of numbers that sum up to n number I have this following code which find every possible pair of numbers that sum up to n number

lst = [int(input()) for i in range(int(input()))]
num = int(input()) #Amount to be matched
cnt = 0
lst = list(filter(lambda i: i &lt;= num, lst)) #Remove number that more than `num`
for i in lst:
    for j in lst:
        if i+j == num:
            cnt += 1
print(int(cnt/2))


For example, if I enter

5 #How many numbers
1 &lt; #Start of number input
4 &lt;
5
7
1 &lt; #End of number input
5 #Amount to be matched


It will return 2 because there is two pair that their sum is equal to 5 (1,4) and (4,1) (The number I marked with &lt; ).

The problem is the complexity is O(n2) which will run slow on large input. I wanted to know if that is there a way to make this run faster?

Another example:

10 #How many numbers
46 #Start of number input
35
27
45
16
0 &lt;
30 &lt;
30 &lt;
45
37 #End of number input
30 #Amount to be matched


The pair will be (0, 30) and (0, 30) which will return 2.
Removing numbers greater than the target affects the correctness of this program - they could be added to negative numbers to reach the target.

You could get a performance improvement by finding the difference between each element and the target, then looking to see if that difference is in the list.  This doesn't in itself reduce the computational complexity (it's still O(n²)), but we can build on that: if the list is first sorted, and we then use a binary search to test membership we get to O(n log n); if we convert to a structure with fast lookup (such as a collections.​Counter, which has amortized O(1) insertion and lookup), then we come down to O(n).

If we have a Counter, then we can account for all combinations of that pair by multiplying one count by the other (but we'll need to consider the special case that the number is exactly half the target).

We could do with some auto tests.  Consider importing the doctest module and using it.  Some good test cases to include:

1, [] → 0
1, [1] → 0
1, [0, 1] → 1
0, [-1, 1] → 1
0, [0, 1] → 0
4, [1, 4, 3, 0] → 2
4, [1, 1, 3, 3] → 4
4, [2, 2, 2, 2] → 6