Как проверить все варианты пар чисел в массиве?

Что проверяют

Умеете ли вы уточнить задачу и уйти от полного перебора там, где он не нужен. «Проверить все пары» чаще всего означает «найти пары с заданной суммой», и следом спрашивают про сложность и про вариант с отсортированным массивом.

Как отвечать

Сначала задайте вопросы: нужна одна пара или все, считать ли (a, b) и (b, a) одной парой, можно ли брать элемент сам с собой, что делать с дубликатами. От ответов зависит решение.

• полный перебор: itertools.combinations(arr, 2) или два цикла, где внутренний начинается с i + 1. Пар ровно n*(n-1)/2, время O(n²), дополнительная память O(1). combinations работает по позициям, поэтому одинаковые значения дадут повторяющиеся пары. permutations вернёт упорядоченные пары, product(arr, repeat=2) добавит пары элемента с самим собой;
• множество просмотренных: один проход, для каждого x проверяем, есть ли в seen число target-x, и только потом добавляем x. Время O(n), память O(n). Чтобы посчитать количество пар с учётом повторов, вместо множества берут Counter или словарь частот;
• два указателя: после sorted() за O(n log n) идём с двух концов и сдвигаем левый или правый указатель в зависимости от суммы. Удобно, когда нужны уникальные пары значений.

Если задача действительно про все пары, например попарные расстояния, то O(n²) неизбежно: самих пар столько. Тогда выигрыш даёт не алгоритм, а векторизация в NumPy через broadcasting или scipy.spatial.distance.pdist.

Проговорите крайние случаи: пустой список, один элемент, повторы, отрицательные числа.

Где спотыкаются

Пишут оба цикла по range(n). Получают пару элемента с самим собой и каждую пару дважды.

В решении с множеством сначала добавляют x, потом проверяют. При сумме, равной удвоенному x, находится «пара» из одного элемента.

Считают, что combinations быстрее вложенных циклов по сложности. Это тот же O(n²), просто генерация идёт на C и лениво. А list(combinations(...)) на большом массиве ещё и забьёт память.