由给定数字相加形成的所有可能数字

Question

如果我有n-r数字，从1到n，其中r数字在两者之间缺失，那么我如何计算所有可能的数字，可以从这些数字的加法中形成（2/3/4/5/6...)。

例如，假设我有5-2数字，即缺少1 2 4和3 5。现在，我可以形成

1 - {1}
2 - {2}
3 - {1,2}
4 - {4}
5 - {1,4}
6 - {4,2}
7 - {1,2,4}
8 - Cannot be formed

这是我需要找出的，这是我无法使用给定数字组合形成的1中的第一个数字。一个简单的逻辑就可以了。谢谢！

Answer 1

1. 从包含0的集合开始
2. 找到set和你的第一个数字的所有可能的和（所以如果你的第一个数字是1，那么你的set包含1和0）
3. 现在添加下一个数字（所以如果您的下一个数字是2，您的set包含0、1、2和3）
4. 所以...

该集包含所有可能的数字。您需要遍历集，找到第一个间隙。即使你的集合中有负数，这也会起作用。

我知道你说过你只是想了解逻辑，但如果你想在下面看到一个解决方案鼠标：

<代码>设置

如果您试图使用STL算法实现set中的间隙搜索，我发现这有点困难。问题是您需要将迭代器的增量与其比较分开。

例如，这将不起作用：

<罢工>

因为如果所有数字都是连续的，则prev（i）1是集合中的最后一个值。

此选项将起作用：

i = foo.begin();
while (i != prev(foo.end()) && *i + 1 == *next(i)){
    ++i;
}
cout << "First number that cannot be formed " << *i + 1 << endl;

但这假设您的集始终包含至少0。

Answer 2

让S[i]是可以由您的数字的第一个i形成的数字集。然后给定S[i]，很容易构造S[i 1]：从S[i]开始，然后添加s r形式的所有数字，其中s在S[i]中，r是（i 1）-列表中的第10个数字。

因此，您可以迭代地构建集s[0]={0}，s[1]，。。。，S[n-r]，并且包含所有可能的和。

以下是您的示例的效果：

S[0] = {0}
r = 1: S[1] = {0} union {0+1} = {0,1}
r = 2: S[2] = {0,1} union {0+2,1+2} = {0,1,2,3}
r = 4: S[3] = {0,1,2,3} union {0+4,1+4,2+4,3+4} = {0,1,2,3,4,5,6,7}

Answer 3

逻辑是从1开始为每个连续整数构建所有可能的和。通过跟踪所有可能的和并只检查整数对的和，可以简化该问题。伪代码（未测试和有缺陷）看起来像：

const std::vector<unsigned> l = {1,2,4};
const unsigned sum = std::accumulate(l.begin(), l.end());
typedef std::vector<unsigned> Sum; // one possibility for a single value
typedef std::vector<Sum> Sums; // all possibilities for a single value
// the element all[i] will provide all possible subsets where the sum is equal to 'i'
std::vector<Sums> all(sum + 2); // we know that sum + 1 is impossible
// initialize with single values
for (auto i: l)
{
    all[i].push_back(Vector(1, i));
}
unsigned i = 1; // ignore 0
// stop as soon as a value doesn't have any subset
while (!all[i].empty())
{
    ++i;
    for (unsigned j = 1; i/2 > j; ++j)
    {
        const unsigned k = i - j;
        // as i == j+k, create all the relevant combinations
        for (const auto &sj: all[j])
        {
            for (const auto &sk: all[k])
            {
                all[i].push_back(sj);
                all[i].back.insert(all[i].end(), sk.begin(), sk.end());
            }
        }
    }
    if (0 == (i % 2))
    {
        // create all the possible decompositions out of i/2
        for (auto left = all[i/2].begin(); all[i/2].end() != left; ++left)
        {
            for (auto right = left + 1; all[i/2].end() != right; ++ right)
            {
                all[i].push_back(*left);
                all[i].back.insert(all[i].end(), right->begin(), right->end());
            }
        }
    }
}

需要解决的错误之一是：拒绝同一数字多次出现的总和。