“空间置换”问题中O(2^n)是如何实现的？

Question

问题陈述基本上是：给定一个字符串，返回所有可能的排列，其中字母之间添加（或不添加）空格

示例： 输入：ABC； 输出：ABC、A BC、AB C、A B C；

我最初在 geeksforgeeks 中找到它，他们的解决方案是 O(n*(2^n))。不过我记得在某个地方看到过 O(2^n) 的解决方案，其中 n 是原始字符串的长度。

list<string> getPermutations(string input, list<string>& permutations, int i = 1){
    if (permutations.empty() ==  true || input != permutations.back()){
        permutations.push_back(input);
    }
    if (i >= input.size()){
        return permutations;
    }
    getPermutations(input, permutations, i+1);
    input.insert(i, " ");
    getPermutations(input, permutations, i+2);
    return permutations;
}

这是我写的解决方案，根据聊天 gpt，“input.insert”使其 O(n*(2^n)) 。这是真的？我怎样才能做到O(2^n)？

Answer 1

让我们考虑长度为 3 ABC 的字符串，它有 2 个可以插入空格的地方：A_B_C

让我们将不存在的空间表示为 0，将存在的空间表示为 1

所以，我们有 4 种可能的变体：

00 ABC
01 AB_C
10 A_BC
11 A_B_C

是不是很像0,1,2,3的二进制表示？另请注意 2^2-1 = 3

所以，让我们尝试一下字符串长度为 4 ABCD，它有 4-1 个空格位置

000 ABCD
001 ABC_D
010 AB_CD
011 AB_C_D
100 A_BCD
101 A_BC_D
110 A_B_CD
111 A_B_C_D

再次，它看起来像0,1,2,3,4,5,7的二进制表示，注意2^3-1=7

所以，只需从 0 到 2^(length-1)-1（含）循环并分析每一位，如果是 1 - 插入空格

总运行时间复杂度为 (2^(N-1))*(N-1)，即 O(2^N)，其中 N 是字符串长度