如何使用 LINQ 找到 ±1 ± 2 ± 3 ± ... ± n = k 形式的所有可能组合？

Question

我很难想出一个在 C# 中使用 LINQ 的简单解决方案来解决这个问题：

对于两个给定的数字 n 和 k，找出形式为 ±1 ± 2 ± 3 ± ... ± n = k 的所有可能组合。

例如，对于 n = 5 和 k = 3，结果将是 "-1+2+3+4-5 = 3", "-1+2+3+4-5 = 3"

public static void Main()
{
    int firstNNumbers = Convert.ToInt32(Console.ReadLine());
    int numberOfOperations = firstNNumbers - 1;
    int targetSum = Convert.ToInt32(Console.ReadLine());
    char[] set = { '+', '-' };
    bool hasSolution = false;
    GetAllOperatorCombinations(set, numberOfOperations, targetSum, ref hasSolution);
    if (hasSolution)
    {
        return;
    }
    Console.WriteLine("N/A");
}
public static int CheckIfGoodAndPrint(string prefix, int targetSum, ref bool hasSolution)
{
    const int Number = 2;
    int thisSum = 1;
    if (prefix == null)
    {
        return -1;
    }
    for (int i = 0; i < prefix.Length; i++)
    {
        if (prefix[i] == '-')
        {
            thisSum -= i + Number;
        }
        else
        {
            thisSum += i + Number;
        }
    }
    if (thisSum != targetSum)
    {
        return -1;
    }
    PrinEquation(prefix, targetSum);
    hasSolution = true;
    return 1;
}
static void GetAllOperatorCombinations(char[] set, int k, int targetSum, ref bool hasSolution)
{
    int n = set.Length;
    GetAllOperatorCombinations(set, "", n, k, targetSum, ref hasSolution);
}
static void GetAllOperatorCombinations(char[] set, string prefix, int n, int k, int targetSum, ref bool hasSolution)
{
    if (k == 0)
    {
        int test = CheckIfGoodAndPrint(prefix, targetSum, ref hasSolution);
        return;
    }
    for (int i = 0; i < n; ++i)
    {
        string newPrefix = prefix + set[i];
        GetAllOperatorCombinations(set, newPrefix, n, k - 1, targetSum, ref hasSolution);
    }
}
private static void PrinEquation(string prefix, int targetSum)
{
    string equation = "";
    for (int i = 1; i <= prefix.Length; i++)
    {
        equation += i + " " + prefix[i - 1] + " ";
        if (i == prefix.Length)
        {
            equation += (i + 1) + " = " + targetSum;
        }
    }
    Console.WriteLine(equation);
}

这是适用于所有情况的代码，但我知道使用 linq 可以缩短很多时间。

Answer 1

这是一个可能的迭代解决方案：

using System;
using System.Linq;

public class Program
{
    public static void Main()
    {
        const int N = 5, K = 3;

        // 1 represents +, 0 represents -
        var results = Enumerable.Range(0, 1 << N)
            .Select(bits =>
            {
                var permutation = Enumerable.Range(0, N)
                    .Select(n => (bits & (1 << n)) != 0 ? (n + 1) : -(n + 1))
                    .ToList();

                var sum = permutation.Sum();
                var str = string.Join(" + ", permutation);

                return new {sum, str};
            })
            .Where(intermediate => intermediate.sum == K)
            .Select(intermediate => $"{intermediate.str} = {K}");

        Console.WriteLine(string.Join("\n", results));
    }
}

这利用了这样一个事实，即可以遍历从 0 到 2^N - 1 的所有整数的二进制表示，以生成+或-（在这种情况下，分别由位 1 和 0 表示）的所有可能排列。

这基本上将这个问题变成了一个循环。

为什么这样做很直观；简而言之，二值类型有 2^N 个可能的 N 长度序列，并且在 0 和 2^N - 1 之间也有 2^N 个整数（显然），因此必须准确地遇到每种可能性一次。

对于您的输入 N = 5 和 K = 3，这会产生（ideone）

-1 + 2 + 3 + 4 + -5 = 3
1 + -2 + 3 + -4 + 5 = 3
-1 + -2 + -3 + 4 + 5 = 3