Как быстро выбрать все сочетания из массива (комбинаторика)? День добрый! Стандартная задача. Есть массив [1,2,3], есть n = 2. Нужно выбрать все сочетания из массива по n. То есть должны получить: [[1,2], [1,3], [2, 3]].
Можно, конечно, пройтись циклом в цикле, но при увеличении размера массива и n вычисления будут выполняться слишком долго ввиду большого количества (> 66%) отсева ненужных сочетаний.
Таки вопрос, как грамотно это реализовать?

Предыдущий
вопрос Следующий
вопрос

Есть несколько способов решения данной задачи более эффективным способом, не используя перебор всех возможных комбинаций.

Один из способов - использовать рекурсивный подход. Можно рассматривать каждый элемент массива как "включенный" или "не включенный" в текущую комбинацию. Таким образом, можно генерировать все возможные сочетания за линейное время.

Вот пример кода на Python:

def combine(nums, n):
def backtrack(start, curr):
if len(curr) == n:
result.append(curr[:])
return
for i in range(start, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
result = []
backtrack(0, [])
return result
nums = [1, 2, 3]
n = 2
print(combine(nums, n))

Этот код будет генерировать все сочетания из массива по n за линейное время.