从数字数组中找到所有加法和减法组合
本文关键字:组合 数组 数字 | 更新日期: 2023-09-27 18:36:36
我需要创建一个函数来接收数字数组和一个目标数字,并返回可以添加或减去这些数字的不同方式来获得目标数字。
即。
值 = 2, 4, 6, 8 目标 = 12
2 + 4 + 6 = 12,
4 + 8 = 12,
6 + 8 - 2 = 12,
2 - 4 + 6 + 8 = 12,
返回 4
这是我到目前为止所拥有的,但它只计算加法问题。
private void RecursiveSolve(int goal, int currentSum, List<int> included, List<int> notIncluded, int startIndex)
{
for (int index = startIndex; index < notIncluded.Count; index++)
{
int nextValue = notIncluded[index];
if (currentSum + nextValue == goal)
{
List<int> newResult = new List<int>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum - nextValue == goal)
{
List<int> newResult = new List<int>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
if (currentSum - nextValue < goal && currentSum - nextValue > 0 )
{
List<int> nextIncluded = new List<int>(included);
nextIncluded.Add(nextValue);
List<int> nextNotIncluded = new List<int>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum - nextValue, nextIncluded, nextNotIncluded, startIndex++);
}
if (currentSum + nextValue < goal)
{
List<int> nextIncluded = new List<int>(included);
nextIncluded.Add(nextValue);
List<int> nextNotIncluded = new List<int>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum + nextValue, nextIncluded, nextNotIncluded, startIndex++);
}
}
}
好吧,简单的方法是尝试所有组合。如果你有 N 个数字,你就有 3^N 个组合。理由是这样的:你对数字求和,但在每个数字前面放一个系数。如果您的号码是 A1..AN,你加上 N 个系数 (C1..CN)和总和:
Sum (Ai*Ci)
您的 CIS 可以是 1(表示您添加数字)、-1(表示您减去数字)或 0(表示您忽略数字)。
因此,检查所有 3^N 可能的系数分配,计算总和并与您的目标进行比较。
我假设所有数字都不同(如您的示例所示)。如果一个数字可以出现两次,您需要考虑到这一点。