3

Given input: N = 6, X = 3

The output should be:

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

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

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

So far I could manage this:

    //returns a string of numbers from 1 to N
static string Numbers(int maxNumber) => maxNumber > 1 ? Numbers(maxNumber - One) + maxNumber :"1";

and a function that generates all possible combinations for +- but the problem is that I want to combine the +- resulted string with numbers from 1 to N:

static void Permute(char[] arry, int i, int n)
        {
            int j;
            if (i == n)
                Console.WriteLine(arry);
            else
            {
                for (j = i; j <= n; j++)
                {
                    Swap(ref arry[i], ref arry[j]);
                    Permute(arry, i + 1, n);
                    Swap(ref arry[i], ref arry[j]); //backtrack
                }
            }
        }

        static void Swap(ref char a, ref char b)
        {
            char tmp;
            tmp = a;
            a = b;
            b = tmp;
        }
SamSon
  • 39
  • 4
  • 1
    The term to search for is "Permutations" – Klaus Gütter Nov 29 '21 at 06:45
  • Why do you not consider the combinations containing `-1`? All other values can be negative, why not the `1`. For instance `-1-2+3+4+5-6` also equals `3` – derpirscher Nov 29 '21 at 07:00
  • You're not really after a "permute" in the regular sense. This *could* be considered as "nCr" with r=N-1, n=2*r, and a bucket of r `+` and r `-`, but there's an easier way: "binary" - see my answer below – Marc Gravell Nov 29 '21 at 07:04
  • Perhaps you don't need to do it with chars, just have an array of 6 numbers, all positive, then sum them and check the answer, then undergo a process where you multiply the first number by -1, sum and check, then multiply the first and second by -1, sumcheck, then multiply the first by -1 again and check, then do first/second/third, then do first, first/second/third, first/second/third/fourth... it's like counting in binary: 0000 (none are multiplied by -1), 0001 (first is * -1), 0010, (first and second), 0011 (first), 0100 (first/sec/thir), 0101, 0110, 0111, etc all combinations of +- – Caius Jard Nov 29 '21 at 07:12
  • Or, if it makes it easier in your mind, have an incrementing number from 0 to 2^6, bitshift it right for every number from 0 to 5 and check if the result is odd. If it is, that number index in the array needs flipping to the negative of itself. Start out with a positive array each time – Caius Jard Nov 29 '21 at 07:17
  • `public static IEnumerable> AllCombinations(int n, int k) => from i in Enumerable.Range(0, 1 << n) let r = Enumerable.Range(0, n).Select(j => (j + 1) * ((i & 1 << j) == 0 ? 1 : -1)) where r.Sum() == k select r;` – Enigmativity Nov 29 '21 at 07:31

1 Answers1

0

This looks like a very different form of "permute". For N integers, you have D=N-1 decisions to make, each of which can be either a + or a -. Two options is: "binary", so, if this is me, I would compute (2^D)-1 (which gives us the upper bound), then do a for loop from zero to that number (inclusive), and do the math: each binary digit is a decision point, and we could say 0===- and 1===+; see what the result is: if it is the number you wanted: log it.

For N=6 we have D=5, and 32 attempts to do; 0 thru 31:

int N = 6, X = 3;

// how many decisions is that?
var decisions = N - 1;

// treat each -/+ as one of "decisions" binary digits
var binaryUpperLimit = (1 << decisions) - 1;
for (int i = 0; i <= binaryUpperLimit; i++)
{
    // compute the sum
    int sum = 1; // the 1 is a permenant fixture, it seems

    // determine each decision using binary arithmetic
    for (int place = 0; place < decisions; place++)
    {
        int digit = place + 2;
        if ((i & (1 << place)) == 0)
        {
            sum -= digit;
        }
        else
        {
            sum += digit;
        }
    }

    // is that what we wanted?
    if (sum == X)
    {
        // we have a "hit"; repeat the above to output this
        Console.Write("1");
        for (int place = 0; place < decisions; place++)
        {
            if ((i & (1 << place)) == 0)
            {
                Console.Write(" - ");
            }
            else
            {
                Console.Write(" + ");
            }
            int digit = place + 2;
            Console.Write(digit);
        }
        Console.Write(" = ");
        Console.WriteLine(sum);
    }
}

(if the initial 1 can be negative, you'll need to adjust to add an extra decision, start the sum at zero, and make digit be +1 instead of +2)

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900