Question

请C++高手帮我看一个问题

这个程序就是找到1~n中等和的两个子集的构成方法个数。如果输入3，就返回1，因为只有1,2和3这一种划分方式。我是想用生成树来写，（我知道方法有点复杂了，，）。构建生成树的边界条件就是剩余元素的个数为0或者已经选择的元素之和大于所有数之和的一半。现在这个构造生成树的程序在调试中发现是有问题的，就是每次根结点传入之后，结点中表示剩余元素数组的指针的指向以及已经选择元素数组的指针的指向都会发生改变，但是按道理来说是不会变的。他们的改变导致之前存储的元素均发生了变化，最后程序出错。还有一个就是new的时候，结点中的指针的指向也会发生变化。所以想请教一下这个问题的原因是什么，解决办法是什么？

void CreateTree(Node* T)
{
//如果剩余元素数组为空，则此结点为叶子结点
if (T->m_Left[0] == 0)
{
T->LeftNode = NULL;
T->RightNode = NULL;
}
//如果剩余元素数组不为空，则左结点选择双亲结点剩余元素数组的第一个元素，右结点放弃双亲结点的剩余元素数组的第一个元素。
//生成左结点后判断sum是否大于FLAG，如是，则左结点置空。
//因为剩余元素的第一个是剩余元素中最小的一个，所以之后的左结点均不出现，也即之后的均不符合要求，所以此节点可视为子结点
else
{
//生成左结点
Node* LeftTemp = new(Node);
LeftTemp->m_SelectCount = T->m_SelectCount + 1;
LeftTemp->m_LeftCount = T->m_LeftCount - 1;
for (int i = 0; i < T->m_SelectCount; i++) //复制双亲结点中已经选择的元素
LeftTemp->m_Select[i] = T->m_Select[i];
LeftTemp->m_Select[LeftTemp->m_SelectCount - 1] = T->m_Left[0]; //从双亲结点剩余的元素中选出第一个元素
LeftTemp->Sum(); //计算左结点已选元素的和
if (LeftTemp->m_Sum > FLAG)
{
T->LeftNode = NULL; //左结点置空
T->RightNode = NULL; //右结点置空
}
else
{
for (int i = 0; i < LeftTemp->m_LeftCount; i++)
LeftTemp->m_Left[i] = T->m_Left[i + 1]; //复制双亲结点中剩余元素
T->LeftNode = LeftTemp;

//生成右结点
Node* RightTemp = new(Node);
RightTemp->m_SelectCount = T->m_SelectCount;
RightTemp->m_LeftCount = T->m_LeftCount - 1;
for (int i = 0; i < T->m_SelectCount; i++) //复制双亲结点中已经选择的元素
RightTemp->m_Select[i] = T->m_Select[i];
RightTemp->m_Sum = T->m_Sum; //右结点已选元素的和与双亲结点一致
for (int i = 0; i < RightTemp->m_LeftCount; i++)
RightTemp->m_Left[i] = T->m_Left[i + 1]; //复制双亲结点中剩余元素
T->RightNode = RightTemp;
}

//进行递归
if (T->LeftNode != NULL)
CreateTree(T->LeftNode);
if (T->RightNode != NULL)
CreateTree(T->RightNode);
}
}

Answer 1

涉及到p=np?的问题都tm一想就头疼

Answer 2

直接用DFS不就可以了么