c++ - 在 pushback() 调用 powerset 函数后 vector 大小保持静态

Question

我编写了以下函数，作为 this algorithm/approach 的实现, 生成给定字符串的幂集(所有子集的集合):

vector<string> getAllSubsets(string a, vector<string> allSubsets) 
{   
    if(a.length() == 1)
    {   
    // Base case, 
    allSubsets.push_back("");
    allSubsets.push_back(a);
    }

    else {
        vector<string> temp = getAllSubsets(a.substr(0,a.length()-1),allSubsets);
        vector<string> with_n = temp;
        vector<string> without_n = temp;
        for(int i = 0;i < temp.size()-1;i++) 
        {
            allSubsets.push_back(with_n[i] + a[a.length()-1]);
            allSubsets.push_back(without_n[i]);
        }
    }
    return allSubsets;

}

然而，有人似乎出错了:temp 和 allSubsets 的大小从递归调用到递归调用保持不变，而由于 push_back() 调用。有什么原因会发生这种情况吗？

Answer 1

这是因为你有一个差一个错误。因为这发生在您的 next-to-base 案例中，所以您永远不会插入任何条目。

因为第一个无效索引是 temp.size() , i < temp.size()意味着您将始终拥有有效的索引。减去 1 意味着您缺少 vector 的最后一个元素。

值得注意的是传递 allSubsets in 作为参数有点傻，因为它总是空的。这种算法根本不需要第二个参数。其次，您可以更高效地使用可以为您简单快速地执行重复数据删除的哈希集。