Write number as sum of given integers

Question

Here's the problem.

Write the given number N, as sum of the given numbers, using only additioning and subtracting.

Here's an example:

N = 20
Integers = 8, 15, 2, 9, 10

20 = 8 + 15 - 2 + 9 - 10.

Here's my idea;

First idea was to use brute force, alternating plus and minus. First I calculate the number of combinations and its 2^k (where k is the nubmer of integers), because I can alternate only minus and plus. Then I run through all numbers from 1 to 2^k and I convert it to binary form. And for any 1 I use plus and for any 0 I use minus. You'll get it easier with an example (using the above example).

The number of combinations is: 2^k = 2^5 = 32.
Now I run through all numbers from 1 to 32. 
So i get: 1=00001, that means: -8-15-2-9+10 = -24 This is false so I go on.
2 = 00010, which means: -8-15-2+9-10 = -26. Also false.

This method works good, but when the number of integers is too big it takes too long.

Here's my code in C++:

#include <iostream>
#include <cmath>
using namespace std;
int convertToBinary(int number) {
    int remainder;
    int binNumber = 0;
    int i = 1;
    while(number!=0)
    {
        remainder=number%2;
        binNumber=binNumber + (i*remainder);
        number=number/2;
        i=i*10;
    }
    return binNumber;
}
int main()
{
    int N, numberOfIntegers, Combinations, Binary, Remainder, Sum;
    cin >> N >> numberOfIntegers;
    int Integers[numberOfIntegers];
    for(int i = 0; i<numberOfIntegers; i++)
    {
        cin >>Integers[i];
    }
    Combinations = pow(2.00, numberOfIntegers);
    for(int i = Combinations-1; i>=Combinations/2; i--) // I use half of the combinations, because 10100 will compute the same sum as 01011, but in with opposite sign.
    {
        Sum = 0;
        Binary = convertToBinary(i);
        for(int j = 0; Binary!=0; j++)
        {
            Remainder = Binary%10;
            Binary = Binary/10;
            if(Remainder==1)
            {
                Sum += Integers[numberOfIntegers-1-j];
            }
            else
            {
                Sum -= Integers[numberOfIntegers-1-j];
            }
        }
        if(N == abs(Sum))
        {
            Binary = convertToBinary(i);
            for(int j = 0; Binary!=0; j++)
            {
                Remainder = Binary%10;
                Binary = Binary/10;
                if(Sum>0)
                {
                    if(Remainder==1)
                    {
                        cout << "+" << Integers[numberOfIntegers-1-j];
                    }
                    else
                    {
                        cout << "-" << Integers[numberOfIntegers-1-j];
                    }
                }
                else
                {
                    if(Remainder==1)
                    {
                        cout << "-" << Integers[numberOfIntegers-1-j];
                    }
                    else
                    {
                        cout << "+" << Integers[numberOfIntegers-1-j];
                    }
                }
            }
            break;
        }
    }
    return 0;
}

Answer 1

Since this is typical homework, I'm not going to give the complete answer. But consider this:

K = +a[1] - a[2] - a[3] + a[4]

can be rewritten as

a[0] = K
a[0] + a[2] + a[3] = a[1] + a[4]

You now have normal subset sums on both sides.

Answer 2

So what you are worried about is you complexity .

Lets analyse what optimisations can be done.

Given n numbers in a[n] and target Value T;

And it is sure one combination of adding and subtracting gives you T ;

So Sigma(m*a[k]) =T where( m =(-1 or 1) and 0 >= k >= n-1 )

This just means ..

It can written as

(sum of Some numbers in array) = (Sum of remaining numbers in array) + T

Like in your case..

8+15-2+9-10=20 can be written as

8+15+9= 20+10+2

So Sum of all numbers including target = 64 // we can cal that .. :)

So half of it is 32 as

Which if further written as 20+(somthing)=32 which is 12 (2+10) in this case.

Your problem can be reduced to Finding the numbers in an array whose sum is 12 in this case

So your problem now can be reduced as find the combination of numbers whose sum is k (which you can calculate as described above k=12 .) For Which the complexity is O(log (n )) n as size of array , Keep in mind that you have to sort array and use binary search based algo for getting O(log(n)).

So as complexity can be made from O(2^n) to O((N+1)logN)as sorting included.

Answer 3

This takes static input as you have provided and i have written using core java

  public static void main(String[] args) {

    System.out.println("Enter number");

    Scanner sc = new Scanner(System.in);

    int total = 0;

    while (sc.hasNext()) {


        int[] array = new int[5] ;

        for(int m=0;m<array.length;m++){
            array[m] = sc.nextInt();
        }

         int res =array[0];
            for(int i=0;i<array.length-1;i++){

                    if((array[i]%2)==1){
                            res = res - array[i+1];
                    }
                    else{
                    res =res+array[i+1];
                    }
            }
            System.out.println(res);
    }
}