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

我想生成一个包含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...
]

什么是有效的方法？ (伪代码或建议是可以的。)

最佳答案

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

// 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];
      }
    }
  }
}

关于algorithm - 查找所有总和为100的4个正整数的列表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34568565/