Как найти все подмножество, которое суммирует его элементы, равно постоянному числу?

Question

Мне нужно найти все подмножества чисел, чтобы получить номер N путем суммирования его элементов. Я не знаю, как пройти эту проблему с комбинацией. В этой комбинации порядок имеет значение для разных чисел.

пример для числа N = 4

1 + 1 + 1 + 1 
2 + 1 + 1 
1 + 2 + 1 
1 + 1 + 2 
2 + 2 
3 + 1 
1 + 3 

Нули не важны для меня. Итак, как я могу получить такие числовые множества, как массив для точного числа?

Answer 1

То, что вы ищете, называется целым числом compositions или заказано partitions.

Композиции могут быть получены рекурсивно (в лексикографическом порядке, если я не ошибаюсь) следующим образом:

public static IEnumerable<List<int>> Compositions(int n) 
{ 
    if (n < 0) 
     throw new ArgumentOutOfRangeException(nameof(n)); 

    return GenerateCompositions(n, new List<int>()); 
} 

private static IEnumerable<List<int>> GenerateCompositions(int n, List<int> comp) 
{ 
    if (n == 0) 
    { 
     yield return new List<int>(comp); // important: must make a copy here 
    } 
    else 
    { 
     for (int k = 1; k <= n; k++) 
     { 
      comp.Add(k); 

      foreach (var c in GenerateCompositions(n - k, comp)) 
       yield return c; 

      comp.RemoveAt(comp.Count - 1); 
     } 
    } 
} 

Не тестировался! Это было расшифровано из реализации Python. Если кто-то хочет внести исправления или обновить код с более идиоматическим C#, не стесняйтесь.

Кроме того, as @aah noted, количество композиций n является 2^(n-1), так что это становится громоздким даже для скромной n.

Answer 2

Если заказ не имеет значения, есть только 2^(N-1) возможности. (В вашем примере нет 2 + 2 или 4)

Затем вы можете представить любую последовательность по его двоичному представлению. Чтобы генерировать, представьте N 1 в строке, так что между ними есть N-1 «пробелы». Выбирая любое подмножество пространств, вы объединяете любые 1, которые смежны через выбранное пространство. Вы можете проверить, что это 1-1 для всех возможных наборов, расширяя любую такую ​​последовательность и вставляя эти пробелы.