c# - 如何计算总数使用 c# 的字符串的可能组合？

Question

我想解决一个我有这个输入的算法:

n = 30 and st = 1234321

现在我想看看使用字符串可以形成多少组合，即 它可以有

(1 2 3 4 2 1)
(1 23 4 3 2 1)
(1 2 3 4 3 21)
(12 3 4 3 2 1)
(12 3 4 3 21)
(1 23 4 3 21)

即都小于 30。所以总组合将为 6。

但是当我们单独出现 0 或像 09 这样的前导时，我们会丢弃计数中的字符串。

以这种情况为例:n = 70 和 st = 8675309。现在在这种情况下我们有:

(8 6 7 5 3 0 9)
(8 67 5 3 0 9)
(8 6 7 53 0 9)
(8 6 7 5 30 9)
(8 6 7 5 3 09)
(8 67 53 0 9)
(8 67 5 30 9)
(8 67 5 3 09)

这里的计数总数仅为 2，因为(如果我们单独出现 0 或像 09 这样的前导，我们不计算)。

请向我推荐用于查找此类组合的 c# 代码。

Answer 1

您可以将您的空间建模为二叉树:在第 n 层，左 child 加入第 n 和 n+1 列表中的第 th 个数字，而右 child 没有。使用 DFS 并修剪您的约束非法的分支，然后计算叶节点。