如何找到所有元素之和等于常数的子集？

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

如果顺序无关紧要，则只有 2^(N-1) 种可能性。（您的示例没有 2 + 2 或 4）

然后您可以用二进制表示来表示任何序列。生成，假设连续有N个1，那么它们之间就有N-1"spaces"个。选择 space 的任何子集，您可以合并通过所选 space 相邻的任何 1。您可以通过扩展任何此类序列并插入这些 spaces.

来验证这是所有可能集合的 1-1

Answer 2

您要查找的是整数 compositions, or ordered 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# 进行更正或更新代码，请随意。

此外，，n的组合数是2^(n-1)，所以即使是适度的n，这也变得笨拙。

如何找到所有元素之和等于常数的子集？

How to find all subset which is the summation of its elements equals to a constant number?

c#

combinations

subset-sum