A traditional way to debug programs is to carefully place print-statements here and there. However, as the amount of printed text increases the ability to filter out and understand the important information decreases. For this reasons, I have searched on how to use ANSI color codes in Java and found a nice implementation in Jlibs. Unfortunately this library did way more than what I needed, and therefore I have stripped it down into a small class that wraps a text string to add color codes and attributes. Feel free to use it and thanks a lot to the original author :-)

Task: Given an unsorted array of integers, find the k-th smallest entry.

Solution: this can be viewed as a reduce-and-conquer problem. The key-idea is to select an element as pivot and split the array into two sub-arrays, smaller (A) and greater (B) than pivot. Then, as long the length of A is greater or equal to k, we delegate the task to this array. Otherwise, we check if the rank of the smallest entry in B is greater or equal to k in the original array (n-|B|). If so, delegate the problem to B with k’ = k-(n-|B|). Otherwise, return the pivot value.

The worst case time of this method is O(n^2), for more information see the Wikipedia article.

Finding all possible, non-empty subsets of an array is actually a really simple task. Everything you need is a counter between 1 and 2^n-1, where n is the number of entries. For each possible value of the counter check it’s bits - 1 at position i means that i’th value of the array is present in the particular subset. No recursion, only shifts and additions.

int[] numbers = { 1, 2, 3, 4 };
int n = numbers.length;
int np = 1 << n;
for (int i = 1; i < np; i++) {
	int bitv = i;
	int pos = 0;
	while (bitv > 0) {
		if ((bitv & 1) == 1) {
			System.out.print(numbers[pos] + " ");
		}
		bitv >>= 1;
		pos++;
	}
	System.out.println();
}

I haven’t been programming algorithms for fun for the last 4, maybe 5 years. At the moment I have realized that it could be a good thing to do… So this is the first try :)

Give you a number N, print all valid combinations of ( and ). e.g.N == 1, then print () N == 2, then print ()(), (()) N == 3, then print ()()(), (())(), ()(()), ((())) N ==.

###The idea: Sequences can be viewed as numbers: 1 : 1 , 2 : 11 2, 3: 111 12 21 3, etc. This has a nice recursive property, for an x we take all the numbers y in [1,x] and append in in front of the solution for (x-y). Except x=1 and 0, which give “1” and “ ” respectively.

A simple solution is as follows:

public class Balls {
	public static String balls(int x) {
		String ret = "";
		for (int i=1; i<=x; i++) ret += "(";
		for (int i=1; i<=x; i++) ret += ")";
		return ret;
	}

	public static String print(String prefix, int x) {
		if (x == 0) {
			return prefix + " ";
		} else if (x == 1) {
			return prefix + "() ";
		} else {
			String ret = "";
			for (int i = 1; i <= x; i++){
				ret += prefix + print(balls(i), x - i);
			}
			return ret;
		}
	}

	public static String print(int x) {
		return print("", x);
	}

	public static void main(String[] args) {
		System.out.println(1 + ":" + print(1));
		System.out.println(2 + ":" + print(2));
		System.out.println(3 + ":" + print(3));
		System.out.println(4 + ":" + print(4));
	}
}

Now, the problem with this solution is recursion and repeated calls to same print(String,int) and balls(int). The running time is O(2^n). A better solution is as follows (perhaps ArrayList can be swaped out with an array):

public static String printDP(int x) {
	ArrayList prints[] = new ArrayList[x + 1];
	if (x == 0) {
		return "";
	} else if (x == 1) {
		return "()";
	}
	prints[0] = new ArrayList();
	prints[0].add("");
	prints[1] = new ArrayList();
	prints[1].add("()");
	String pres[] = new String[x + 1];
	pres[0] = "";
	for (int i = 1;i <= x; i++) {
		pres[i] = "(" + pres[i - 1] + ")";
	}
	for (int i = 2; i <= x; i++) {
		prints[i] = new ArrayList();
		for (int j = 1; j <= i; j++) {
			for (String s : prints[i - j]) {
				prints[i].add(pres[j] + s);
			}
		}
	}
	String ret = "";
	for (String s : prints[x]) {
		ret += s + " ";
	}
	return ret;
}

The running time is O(n^3).