Here is a typical algorithmic problem I encounter when interviewed:

Write a program that receives a set of positive integers

(duplicates are possible) and decides if the set of integers can be divided into three subsets with the same sum of elements. For instance, {1,1,1} can be divided into three subsets with equal sum {1} {1} {1}, {3,2,5,4,1,3} can also be divided into three subsets with equal sum {1, 5}, {2, 4}, {3, 3}. {2,3,4,5} however canot be divided into three subsets with equal sum.

The problem can be easily solved using recursion but on an interview it is sometimes easier to come up with a non-recursive solution.

**The algorithm:**

total sum of elements is not divisible by 3 without reminder, the subsets do not exist.

true, otherwise continue to the next number.

**The**

theory:

theory:

group of objects (positive numbers in our case) we want to find all the

possible ways to divide the objects between 3 different buckets. Lets number

the buckets 0, 1, and 2, and lets assume for now that buckets are allowed to be

empty but each object must be in one of the buckets.

many ways are there to arrange 1 object into 3 buckets? The answer is 3 because

the object can be placed in either one of the buckets. And using our notation:

0 – object is in the first bucket, 1 – object is in the second bucket, 2 –

object is in the third bucket.

objects we have 9 arrangements:

both objects are in the first bucket

the first object is in the first bucket and the second object is in the second

bucket

the first object is in the first bucket and the second object is in the third

bucket

the first object is in the second bucket and the second object is in the first

bucket

both objects are in the second bucket

the first object is in the second bucket and the second object is in the third

bucket

the first object is in the third bucket and the second object is in the first

bucket

the first object is in the third bucket and the second object is in the second

bucket

both objects are in the third bucket

the similar logic for 3 objects we would have 27 arrangements:

n objects we would have 3^n arrangements. If we look at our example with 3

objects we might notice that we start counting from 0, and go up all the way to

2 and then suddenly go to 10 instead of 3. It actually looks like all the

digits above 2 are missing. And there is a good reason why they are missing. We

count in ternary numeral system or simply base 3.

find all the possible ways to divide a set of objects between 3 different buckets

we just have to count in base 3. And to while we count we can calculate the

total sum of all numbers in each bucket. For example for base 3 number

010011202 and a set of positive numbers 2,4,3,7,8,2,7,2,7 we would calculate

the sum for the first bucket 2+3+7+2, second bucket 4+8+2, and third bucket 7+7

and see that all sums are equal to 14.

course our solution is suboptimal because we only care about the sum of each

group and do care about the bucket order. 010011202 and 101100212 is the same

number for our purposes because nothing changes if we switch the buckets.

fact, to calculate what the number of unique combinations is equal to we would have to learn

**Java implementation:**

import java.util.ArrayList;

import java.util.Iterator;

import java.util.List;

public class Main {

/**

* @param args

*/

public static void main(String[] args) {

// List Example implement with ArrayList

List<Integer> numbers = new ArrayList<Integer>();

numbers.add(3);

numbers.add(4);

numbers.add(3);

numbers.add(10);

numbers.add(1);

numbers.add(2);

numbers.add(3);

numbers.add(4);

numbers.add(7);

numbers.add(7);

numbers.add(7);

int n = numbers.size();

int count = (int) Math.pow(3, n);

for (int i = 0; i < count; ++i)

{

String base3 = Integer.toString(i,3);

base3 = padLeft(base3, n);

//System.out.println(“base3:” + base3);

int [] group = {0, 0, 0};

int k = 0;

Iterator<Integer> it=numbers.iterator();

while(it.hasNext())

{

int groupId = Integer.parseInt(base3.substring(k,k+1));

Integer value=(Integer)it.next();

group[groupId] += value;

++k;

}

if (group[0] > 0 && group[0] == group[1] && group[0] == group[2])

{

System.out.println(“base3:” + base3);

}

}

}

public static String padLeft(String s, int n) {

return String.format(“%” + n + “s”, s).replace(‘ ‘, ’0′);

}

}