учитывая набор целых чисел, найдите, можно ли их добавить к числу

Question

У нас есть числа, которые являются суммой этих целых чисел: [1, 2, 4]

Например, 3 (2 + 1), 6 (4 + 2), 5 (1 + 4), 7 (1 + 2 + 4) Номер из списка можно использовать только один раз. Их нельзя повторить.

Теперь мне нужно найти все числа, которые построены таким образом, что включает в себя 2 в их сумме.

Это то, что я написал бы для этого короткого списка :

SELECT * FROM [TABLE] WHERE number = 2
OR number - 2 + 1 = 0  
OR number - 2 + 1 + 4 = 0
OR number - 2 + 4 = 0

Но предположим, что у нас есть 7 чисел в списке [1, 2, 4, 8, 16, 72, 128]

Так что писать подобное было бы явно слишком долго и мне не удается придумать какой-то алгоритм: (

Надеюсь, проблема ясна

Answer 1

Было бы просто так?

SELECT * from [Table] WHERE number & 2 = 2

Он использует побитовое И для поиска чисел, для которых задано 2 бита.

РЕДАКТИРОВАТЬ
Я предполагаю, что список чисел, которые вы используете для создания суммы (1,2,4, ..), - это степени двойки. Вы можете использовать их, чтобы сложить любое (положительное) число. (при условии, что список достаточно длинный), используя каждое число 0 или 1 раз.

Answer 2

Вы можете использовать рекурсивный CTE:

with n as (
      select v.n
      from (values (1), (2), (4)) v(n)
     ),
     cte as (
      select n as num, n as max_n, convert(varchar(max), n) as calculation
      from n
      union all
      select num + n.n, n.n as max_n, concat(calculation, ' + ', n.n)
      from cte join
           n
           on n.n > cte.max_n
     )
select distinct num, calculation
from cte;

Здесь - это скрипт db <>.

Эта версия также включает вычисление. Число может появляться несколько раз, если существует несколько способов представления числа.

Вышеупомянутое генерирует все комбинации. Вы можете отфильтровать те, у которых просто «2», после создания всех из них. Или вы можете обрабатывать «2» отдельно - просто сгенерируйте все комбинации без «2», а затем добавьте «2» к окончательным результатам.