我的回溯函数有问题，它会循环某些数据，我不能在这里写整个程序代码，但可以把我的函数放在这里。
bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen)
{
if(moneyA == half)
return true;
else if(index >= quantity)
return false;
moneyA += values[index];
if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
{
ifChosen[index] = true;
return true;
};
moneyA -= values[index];
if(shareMoney(quantity, values,index+1, moneyA, half, ifChosen))
{
ifChosen[index] = false;
return true;
};
return false;
}
现在解释一下：
quantity -
values
中
的
元素
数指数组值
该函数获取长度为 values 数组的元素的数量，values 一个包含数字的数组，从最高到最低排序，索引控制递归，默认为 0，因此它从第一个元素开始，moneyA 存储数字的变量值数组，它应该达到一半，这是从值数组求和的数字的一半，并且 ifChosen 存储选择的数字。
整个函数执行此操作，它对 values 数组中的元素求和并检查它是否达到一半，如果它低于一半，则将其添加到 moneyA 并在 ifChosen 中标记，然后它转到下一个，如果总和高于它的一半取回并在 ifChosen 数组中取消标记它并从 moneyA 中减去。它应该总是得到最高的元素。
这是一个简单的例子：
6 - number of elements
50, 20, 19, 15, 2, 2 - elements stored in values array
total sum is - 108
half of elements - 54
这个结果应该是：
50, 2, 2 - marked as true in ifChosen
20, 19, 15 - marked as false in ifChosen
当然，对于这个简单的示例，它做得很好，但是对于具有更多数字并且一个数字不止一次出现的更复杂的示例，它循环并且递归永远不会停止。我实际上已经为此工作了 1.5 周，并询问了我所有的朋友，但没有人知道它有什么问题。我知道这与背包问题有点关系，但我还没有那个问题，仍然需要学习。
我期待任何可以提供帮助的答案。
我很抱歉我的标点符号，但我是第一次来这里，不习惯格式化。
这里有一个例子：
89 86 83 67 53 45 5 1
44 43 34 33 33 24 23 23 23 22 21 21 19 12 11 9 8 7 5 3 2 2 2 1 1 1 1 1
real 0m28.007s
user 0m27.926s
sys 0m0.028s
现在我认为它会永远循环：43 个元素：
12 2 2 1 3 4 5 6 7 89 33 12 45 23 44 23 11 44 1 3 5 7 88 33 8 19 43 22 86 5 34 23 21 67 83 24 21 53 9 11 34 1 1
@Karl Bielefeldt 是的，我知道有很多组合，这就是我试图加快速度的原因。现在这就是我所得到的，但它给我某些输入的错误结果。任何人都可以纠正它，它比以前工作得更快吗？
bool shareMoney(int quantity, int *values, int index, int moneyA, int half, bool *ifChosen){
if(index>=quantity && moneyA == half){ return true;}
else if(index>=quantity) return false;
moneyA+=values[index];
ifChosen[index]=true;
if(moneyA<=half){
shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
if(moneyA==half) return true;
return true;
}else{
shareMoney(quantity,values,index+1,moneyA, half,ifChosen);
moneyA-=values[index];
ifChosen[index]=false;
return true;
}
return false;}