algorithm - 硬编码深度优先搜索结果(或优化？)

Question

我需要获取树的所有可能路径，所以我实现了这样的 DFS:

void bisearch(std::vector<int> path, int steps,
                           int node, std::vector<std::vector<int>> *paths) {
  int sum = 0;
  if (path.size() == steps) {
    for(std::vector<int>::iterator it=path.begin(); it != path.end(); ++it) {
        sum += (*it);   
    }
    if (sum == node)
        paths->push_back(path);
  }
  else {
    std::vector<int> uPath(path);
    uPath.push_back(1);
    bisearch(uPath, steps, node, paths);
    std::vector<int> dPath(path);
    dPath.push_back(0);
    bisearch(dPath, steps, node, paths);
  }
}

上面的代码为长度为“steps”的树提供了到某个结束节点的所有路径。然后我循环遍历所有结束节点并运行它以获取每条路径。问题是它需要永远!我在考虑也许对所有可能的组合进行硬编码以加快速度，当然我不能手动执行此操作，因为例如一棵有 25 步的树将有 2^25 ~= 3500 万种可能的组合，但也许我可以打印搜索的输出并将其用于硬编码？或者有人看到我可以做的任何简单的优化都会对性能产生很大的影响吗？谢谢。

编辑:让我澄清一下。我需要路径，即沿着树的移动顺序，其中 1 代表右手移动，0 代表左手移动(或上/下，无论您喜欢什么)。因此，例如一个 2 步树，我需要四个有序对 (1,0) (0,1) (1,1) (0,0)。

Answer 1

由于“所有组合”应该只是“在某个级别右转/左转的组合”，您可以循环遍历 0 到 2 ^ n - 1，并且前面用 0 填充的二进制表示可能随心所欲。

如果你想要的是左转数等于某个数字 k 的路径数，那么这正好等于从 0 到 2 ^ n - 1 的 k 位等于 1 的数字，你可以使用这来计算你想要的结果。