我编写了以下函数,作为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;

}


但是,似乎有人出了问题:tempallSubsets的大小在递归调用到递归调用之间保持不变,而由于push_back()调用它们的大小应该增加。有什么理由会发生这种情况?

最佳答案

这是因为您有一个错误的错误。因为这是在您的下一个基础情况下发生的,所以您永远不会插入任何条目。

由于第一个无效索引是temp.size(),因此i < temp.size()表示您将始终具有有效索引。减1表示您缺少向量的最后一个元素。

值得注意的是,将allSubsets作为参数传递是很愚蠢的,因为它始终为空。这种算法根本不需要第二个参数。其次,使用散列集可以提高效率,该散列集可以轻松,快速地为您执行重复数据删除。

09-06 19:13