CareerCup

public static boolean permute(ArrayList<Integer> prefix, ArrayList<Integer> input){
		int sum1 = sum(prefix);
		int sum2 = sum(input);
		if(sum1 == sum2){
			System.out.println("Sum: "+sum1);
			return true;
		}
		else{
			for(int i=0;i<input.size();i++){
				//remove the element from input to prefix
				prefix.add(input.remove(i));
				
				boolean value = permute(prefix,input);
				
				//add back the value from prefix to input
				input.add(i, prefix.remove(prefix.size()-1));
				
				if(value) return true;
			}
		}
		return false;
	}

	private static int sum(List<Integer> arr) {
		int sum =0;
		for(Integer val : arr){
			sum+=val;
		}
		return sum;
	}

This is called as a partition problem.
It can be solved using dynamic programming.
Also the time complexity is polynomial in n and not 2^n if we have liberty of space. Otherwise we will have to use recursive solution which has time complexity of 2^n.

public class Main {

	public static void main(String[] args) {
		int[] array = {1, 5, 11, 5, 2};
		if(canBePartitioned(array)){
			System.out.println("the given array can be partitioned.");
		}else{
			System.out.println("the given array cannot be partitioned.");
		}
		
	}
	
	public static boolean canBePartitioned(int[] array){
		int sum = 0;
		for(int i=0; i<array.length; i++){
			sum += array[i];
		}
		if(sum%1 == 1){
			return false;
		}
		boolean[][] partition = new boolean[sum/2+1][array.length+1];
		for(int i=0;i<array.length+1;i++){
			partition[0][i] = true;
		}
		for(int i=1;i<sum/2+1; i++){
			partition[i][0] = false;
		}
		for(int i=1; i<sum/2+1; i++){
			for(int j=1; j<array.length+1; j++){
				partition[i][j] = partition[i][j-1];
				if(i >= array[j-1])partition[i][j] = partition[i-array[j-1]][j-1] || partition[i][j];
			}
		}
		return partition[sum/2][array.length];
	}
}

// ZoomBA
l = [ 4, 2, 2, 0, -1, 1 ]
possible = exists ( [1: #|l|] ) :: {
   inx = $.o 
   sum( l[0:inx-1] ) == sum ( l[inx:-1] )
}
println( possible )

Could you provide some clarification because I am not sure that I understand the problem well. If complexity should be 2^n, than we are talking about splitting the list in 2 subsets which have equal sum. I mean we have 1,2,5,4 and we split on {1,5} and {2,4} .Otherwise complexity is linear.
One offtopic question - is it true that you know the status of your interveiw at the end of the day (on site) I mean you are in or out, or this is a myth.

private bool CheckSumHelp(int[] input, int length)
        {

            int[] help = new int[length];
            int p;
            int n = (int)Math.Pow(2, length);

            for (int index = 0; index < n; index++)
            {

                p = 0;
                help[p] = help[p] + 1;
                while (help[p] == 2)
                {

                    help[p] = 0;
                    help[p + 1] = help[p + 1] + 1;
                    p++;
                }

                List<int> left = new List<int>();
                List<int> right = new List<int>();

                for (int i = 0; i < length; i++)
                {

                    if (help[i] == 1)
                    {
                        left.Add(MyArray[i]);
                    }
                    else
                    {
                        right.Add(MyArray[i]);
                    }
                }

                if (left.Sum() == right.Sum())
                {
                    Console.WriteLine("True");
                    Console.ReadLine();
                    return true;
                }
            }
            Console.WriteLine("False");
            Console.ReadLine();
            return false;
        }

Basically, the solution is polynomial as mentioned by the interviewer
Solution: Create subsets of the array (2^n subsets).
For each subset, check the sum of the subset is equal to sum of the other subset (superset - this subset). if yes return true, otherwise false.

int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    bool ok=false;
    // mask reprsents a set
    for(int mask=0;mask<(1<<n);mask++) {
        int left=0,right=0;
        for(int i=0;i<n;i++) {
            // i  bit is set consider it as left pile
            if(mask & (1<<i)) {
                left+=a[i];
            } else {
                // i bit is not set consider as right pile
                right+=a[i];
            }
        }
        if(left==right) {
            ok=true;
            break;
        }
    }
    if(ok) {
        cout<<"Yes\n";
    } else {
        cout<<"No\n";
    }

it is a dynamic programming problem.
let B[i][j] be the true/false value if value i can be represented by elements from an array A[1] to A[j]
then B[i][j] = B[i][j-1] or B[i-A[j]][j-1]
B[s/2][n] contain the final result.

Why not try the following:
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n-1] - a[i] = a[i]

e.g.
-1 1 1 2 2 5
Sums:
-1 0 1 3 5 10

10-5 = 5. we have a winner

e.x2:

-1 -1 1 2 2 2 3 5 6 7
Sums:
-1 -2 -1 1 3 5 13 19 26

26-13 = 13, we have a winner

Why not try the following (nlogn):
1. sort the list
2. find the "sum so far" at each index. i.e. a[i] = Sum(a0...ai)
3. Find the item for which a[n-1] - a[i] = a[i]

e.g.
-1 1 1 2 2 5
Sums:
-1 0 1 3 5 10

10-5 = 5. we have a winner

e.x2:

-1 -1 1 2 2 2 3 5 6 7
Sums:
-1 -2 -1 1 3 5 13 19 26

26-13 = 13, we have a winner

It is a DP problem. Sum the entire array and divide by 2. If the sum is even than use the subset sum problem to search for sum/2. If the sum is odd no solution exists.

This can be done in O(n) time complexity.
1. Sum the whole array as right_sum;
2. Left_sum = 0;
3. At any index compare if left _sum is equal to right_sum and return true if they are equal.
4. At every index right_sum =--a[i] and left_sum+=a[i].
5. After i exhaust return false

hjj

hihi

This is a O(N) solution.
1. get a sum array, where sumArray[i] = sumArray[i-1] + array[i] for all i in array.
2. find the index of sumArray[N] / 2 , say iSplit.
3. Split at iSplit

Hi,
I tried to solve it without permutation. First sort the given array and then divide the array in two sorted vectors. Hence, the resultant sorted vectors will have minimum difference in their total sums.Then recursively I swap the elements till we get the equal sum on both the sides. I keep the vectors sorted so that it becomes easy in swapping the elements.

You can directly copy paste the following code are compile are run it. Please let me know if find any issue.

Time complexity of the following algo in average case should much less than 2^n.

// TwolistEqualSum.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <cmath> 
#include <vector>
using namespace std;



int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}



void SwapItems(vector<int> *v1, int * arry1Total, vector<int> *v2, int * array2Total, int mean)
{

    if ((v1->size() == 0) || (v2->size()==0)) 
    {
        return;
    }

    if (*arry1Total == *array2Total)
    {
        return;
    }

    if (*arry1Total > mean)
    {
        int diff =  *arry1Total - mean;
        int i = 0;
        int temp;

        do
        {

            temp = (*v1)[i];

            *arry1Total = *arry1Total - temp;

            v2->push_back(temp);

            v1->erase(v1->begin() + i);

            *array2Total = *array2Total + temp;

             if (*array2Total == *arry1Total)
             {
                    break;
             }

             diff = diff - temp;
       
        }while (v1->size() > 0 && diff > 0);        

        qsort(&(*v2)[0], v2->size(), sizeof(int), compare);

    }
    else
    {
        int diff = *array2Total - mean;

        int i = 0;
        int temp;
        do
        {
             temp = (*v2)[i];

              *array2Total = *array2Total - temp;

            v1->push_back(temp);

            v2->erase(v2->begin() + i);

             *arry1Total = *arry1Total + temp;

             if (*array2Total == *arry1Total)
             {
                    break;
             }

             diff = diff - temp;
       
        }while (v2->size() > 0 && diff > 0);

         qsort(&(*v1)[0], v1->size(), sizeof(int), compare);

    }

    static int iteration = 0;

    iteration++;

    if (iteration < ((v1->size() + (v2->size()) / 2)))
    {
        SwapItems(v1, arry1Total, v2 , array2Total, mean);
    }

    return;

}


int _tmain(int argc, _TCHAR* argv[])
{
	
    const int inputSize = 22;
    int input[inputSize] = {4,2,2,0,-1,1,10,3,7,15,23,20,3,9,6,199,50,50,50,49,12,2}; // assume the input and its size is known. For testing purpose just change inputSize and input array

    /* Sampe input2
    const int inputSize = 19;
    int input[inputSize] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,1,10}; // assume the input and its size is known. For testing purpose just change inputSize and input array

    */

    vector<int> v1, v2;

    int total = 0;

    cout << " Input list : ";

    for (int i =0 ; i < inputSize; i++)
    {
        total = total + input[i];
        cout << input[i] << " ";
    }

    cout << endl;

    if (total % 2)
    {
        cout << " Not possible to divide the input list";
    }
    else
    {
        qsort(input, inputSize, sizeof(int), compare);     

        int arry1Total = 0;
        int array2Total = 0;
        int mean = 0;

        for (int i =0 ; i < inputSize; i++)
        {
            if (!(i % 2))
            {
                v1.push_back(input[i]);
                arry1Total = arry1Total + input[i];
            }
            else
            {

                v2.push_back(input[i]);

                array2Total = array2Total + input[i];
            }
        }

        mean = (arry1Total + array2Total) / 2;

       SwapItems(&v1, &arry1Total, &v2, &array2Total,  mean);

       
       if (arry1Total == array2Total)
       {

           cout << " List 1: ";

           for ( int k = 0; k < v1.size(); k++)
           {
               cout << v1[k] << "  ";
           }

           cout << " : Total:" << arry1Total;
           cout << endl;

           cout << " List 2: ";
           for ( int k = 0; k < v2.size(); k++)
           {
               cout << v2[k] << "  ";
           }

           cout << " : Total:" << array2Total;
           cout << endl;
       }
       else
       {
            cout << " Not possible to divide the input list";
       }
    }  
   

    int j;

    cin >> j;

       
    return 0;
}

You don't need 0(n2) algorithm for this because it is a partition between prefix and postfix strictly.. what u do is find the get the sum of all the elements in the array (lets call it total_sum). Now start with element 0, and start cumulative sum.. at any time if 2*cumulative sum = total sum, we have the partition.

Thank you for the answers William.
Here is my solution - dynamically programming - partition problem

boolean canSplitEqually(int[] nums) {
	
	  int sum = 0;
	  for ( int item : nums) {
		  sum += item;
	  }
	  if (sum%2 != 0) {
		  return false;
	  }
	  boolean can[] = new boolean[sum+1];
	  can[0] = true;
	  for (int i = 0; i < nums.length; i++) {
		  for (int s = sum; s + 1 >  0; s--) {
			  if (can[s]) {
				  if(s+nums[i] <= sum)
					  can[s+nums[i]] = true;
			  }
		  }
	  }
	  return can[sum/2];
  }