How to solve a recursive problem without using recursion


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:

a)
If
total sum of elements is not divisible by 3 without reminder, the subsets do not exist.
b)
Count in base-3 from 0 to 3^N
c)
For each number sum all digits for each of the three subsets. if all three equal we return
true, otherwise continue to the next number.

The
theory:
For a
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.
How
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.
For 2
objects we have 9 arrangements:
00 –
both objects are in the first bucket
01 –
the first object is in the first bucket and the second object is in the second
bucket
02 –
the first object is in the first bucket and the second object is in the third
bucket
10 –
the first object is in the second bucket and the second object is in the first
bucket
11 –
both objects are in the second bucket
12 –
the first object is in the second bucket and the second object is in the third
bucket
20 –
the first object is in the third bucket and the second object is in the first
bucket
21 –
the first object is in the third bucket and the second object is in the second
bucket
22 –
both objects are in the third bucket
Using
the similar logic for 3 objects we would have 27 arrangements:
000
001
002
010
011
012
020
021
022
100
221
222
And for
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.
So to
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.
Of
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.
In
fact, to calculate what the number of unique combinations is equal to we would have to learn 
Polya’s Counting Theory…

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′);
}

}


Leave a Reply


× five = 25

Pinterest
Email