如何找到所有的子集即所有元素的和等于一个常数

本文关键字：常数 于一个 元素 子集 何找 | 更新日期: 2023-09-27 18:13:57

我需要找到所有的数字子集，通过求和它的元素来得到一个数字N。我不知道怎么解这种组合题。在这种组合中，顺序对不同的数字很重要。

N =数量的示例4 

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

0对我来说不重要。那么我怎样才能把这样的数字集合作为一个数组来表示一个精确的数字呢?

如何找到所有的子集即所有元素的和等于一个常数

您正在寻找的是所谓的整数组合，或有序分区。

组合可以按如下方式递归生成(如果我没记错的话，是按字典顺序生成的):

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#来修改或更新代码，请随意。

此外，正如@aah所指出的，n的组成数是2^(n-1)，因此即使对于适度的n，这也变得笨拙。

如果顺序无关，则只有2^(N-1)种可能性。(你的例子没有2 + 2或4)

你可以用它的二进制表示来表示任何序列。为了生成，假设一行中有N个1，因此它们之间有N-1个"空格"。选择任意空间的子集，合并任意相邻空间中的1。您可以通过展开任何这样的序列并插入这些空格来验证这是1-1到所有可能的集合。

相关文章：