recursion - 用于生成n位字符串的分而治之算法？

Question

有人可以告诉如何生成 n 位字符串（所有可能的组合），即使用分而治之的方法从 0 到 2^n-1 计数位。

我可以使用以下算法做到这一点，但空间复杂度和时间复杂度都是 O(2^n)。有人可以给我一个更好的算法（使用分而治之），它需要比这更少的空间。

ArrayList generate(int n)
 {
      if(n==1) 
         {  
            Create an arrayList and store strings "0" and "1";
         }
     else
    {
         generate(n-1)

         now recompose the solution to get 2^n strings and return this arraylist
         "PROBLEM here is that the length of the array list is also getting
         exponential"

    }
 }

Answer 1

我相信你被误解了。生成位串本身不是问题，因此您无法提出解决方案。也许你遗漏了问题的一部分。例如，您可以使用位串定义解决方案的表示，然后尝试为给定问题找到最佳位串。

还有一件事，通常表示为 n 位字符串的问题的时间复杂度始终为 O(2^n)，除非问题已定义。然后，您可以使用问题的标准来降低任一复杂性。但是在定义问题之前，生成和遍历一个 n 位字符串总是需要您倾向于每一个可能的 2^n 组合。

编辑：

如果必须，这是分治的伪代码：

solution breakdown(problem p)
{
    if (smallenough(p))
    {
        return solve(p);
    }
    problem[] subproblems = divide(p);
    solution[] subsolutions;
    for (i=0; i<count(subproblems); i++)
    {
        subsolutions[i] = breakdown(subproblems[i]);
    }
    return reconstruct(subsolutions);
}