# K-th smallest element

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.

# All subsets of an array

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.

# Playing with code

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 :)

###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:

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):

The running time is $O(n^3)$.