algorithm - 查找和为 100 的 4 个正整数的所有列表

Question

我想生成一个列表，其中包含 4 个正整数的所有可能列表，其总和正好等于 100。 (加数不需要是唯一的。)

可能的示例片段:

[
 // Using (1+1+1+97)
 [1,1,1,97],
 [1,1,97,1],
 [1,97,1,1],
 [97,1,1,1],

 // Using (2+1+1+96)
 [2,1,1,96],
 [2,1,96,1],
 [2,96,1,1],
 [96,2,1,1],

 [1,2,1,96],
 [1,2,96,1],
 [1,96,2,1],
 [96,1,2,1],

 [1,1,2,96],
 [1,1,96,2],
 [1,96,1,2],
 [96,1,1,2],

 // Using (2+2+1+95), etc...
]

执行此操作的有效方法是什么？ (伪代码或建议都可以。)

Answer 1

这是一个适用于任意数量零件的通用解决方案:

// create(100, 4) returns the 156849 solutions
Iterable<List<int>> create(int max, int parts) sync* {
  assert(max >= parts);
  if (parts == 1) {
    yield [max];
  } else {
    for (int i = max - parts + 1; i > 0; i--) {
      yield* create(max - i, parts - 1).map((e) => e.toList()..add(i));
    }
  }
}

以及针对 4 个数字的更优化的解决方案:

// create(100) returns the 156849 solutions
Iterable<List<int>> create(int max) sync* {
  for (int a = 1; a <= max - 3; a++) { // -3 because b/c/d are >= 1
    for (int b = 1; b <= max - a; b++) {
      for (int c = 1; c <= max - a - b - 1; c++) { // -1 because d is >=1
        yield [a, b, c, max - a - b - c];
      }
    }
  }
}