给定数字的组合总计为 X

Question

虽然这应该不是很困难，但我一直坚持这个。我需要在 C 中创建一个函数，计算并显示给定数字的所有可能组合(不重复)，其中每个组合的数字(范围仅从 1 到 9)在相加时给出指定的总和。

我想这不是最清楚的解释，所以这里有一个例子:计算所有 5 个数字(从 1 到 9)的总和为 28 的集合。

如果有人能解释一下，我将非常感激。

Answer 1

由于只有 512 种不同的选择，您可以轻松地预先计算结果。

预先计算:

• 准备一个空 map (sum => set(set(digit)))，命名为lookup。
• 对于 (1..9) 的每个子集
  • 计算其总和。
  • 如果 lookup 没有键 sum，则创建一个新条目，一个空集。
  • 将子集添加到lookup[sum]

要查找总和:

• 如果lookup具有键sum，则返回该条目(的副本)。否则返回一个空集。

<小时/>

解决 C 的一些低级问题:

map int=>x 只是一个数组。一组 x 也只是一个数组 + 长度。

map 的数组可以分配为静态，因为您已经知道最大的键 45。

您也可以预先估计最大的集合，或使用动态分配(更有效)。如果您不关心空间，则可以轻松过度分配(最多 512 个条目)。我想您不想过度分配这么多，所以您也可以学习如何动态分配。

一组数字可以表示为 9 位位掩码(内存中为 16 位)。然后就很容易枚举它们。

用于查找的实际类型的草图:

typedef setOfDigits int16;

struct setOfSets{
  setOfDigits* data;
  int16 count; //the actual amount of sets in the set
  int16 space; //the size of the allocated array
}

setOfSets lookup[46];

查找的实际类型的草图，没有动态分配或struct:

int16 lookup[46][512];
int16 lookupLength[46];

请注意，如果您将 space:=count 等同起来，那么您永远不会过度分配，但您经常重新分配，这更容易实现，但可能效率低下(但代码运行一次，因此嘿)

当然，高级语言(甚至 C++)本身(javascript)或通过标准库(C++、Java)具有动态数组。在 C 中，您必须依赖 realloc。