目前有一個字母陣列：[A,D,F,Z,K,L,O]，要找出它的所有子集，比如子集有[A],[A,D],[Z,
L,O],[D,F,K,O]等等，請使用回溯搜索演算法，按照要求輸出：
長度為0的子集有：1個
長度為1的子集有：7個
長度為2的子集有：21個
長度為3的子集…
…
長度為6的子集有：7個
長度為7的子集有：1個
uj5u.com熱心網友回復：
#include <vector>
#include <iostream>
void BackTrackSubArrays(std::vector<char> &vecTemp, size_t &nCount, size_t nTotal, size_t nBegin, const std::vector<char> &vecArray)
{
if (vecTemp.size() == nTotal)
{
++nCount;
return;
}
for (size_t i = nBegin; i < vecArray.size(); i++)
{
vecTemp.push_back(vecArray[i]);
BackTrackSubArrays(vecTemp, nCount, nTotal, i + 1, vecArray);
vecTemp.pop_back();
}
}
void SubArrays(const std::vector<char> &vecArray)
{
std::vector<char> vecTemp;
vecTemp.reserve(vecArray.size());
size_t nCount = 0;
for (size_t i = 0; i <= vecArray.size(); i++)
{
BackTrackSubArrays(vecTemp, nCount, i, 0, vecArray);
std::cout << "長度為" << i << "的子集有:" << nCount << "個" << std::endl;
nCount = 0;
}
}
int main()
{
SubArrays({ 'A','D','F','Z','K','L','O' }); //此處用到c++11的初始化語法，如果編譯器不支持c++11，請自己構造std::vector<char>輸入
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/239789.html
標籤：C語言