1

数値の配列とターゲット番号を取り込んで、それらの数値を加算または減算してターゲット番号を取得できるさまざまな方法を返す関数を作成する必要があります。

すなわち。

値=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++);
        }
    }
}
4

1 に答える 1

1

簡単な方法は、すべての組み合わせを試すことです。N個の数字がある場合、3^Nの組み合わせがあります。理由は次のとおりです。数値を合計しますが、それぞれの前に係数を置きます。数値がA1..ANの場合、N個の係数（C1..CN）を加算して合計します。

Sum (Ai*Ci)

Cisは、1（数値を加算することを意味する）、-1（数値を減算することを意味する）、または0（数値を無視することを意味する）にすることができます。

したがって、3 ^ Nの可能な係数の割り当てをすべて調べ、合計を計算して、ターゲットと比較します。

私はすべての数字が異なると仮定しています（あなたの例のように）。数字が2回表示される可能性がある場合は、それを考慮する必要があります。

于 2012-06-08T06:13:05.197 に答える