Subsets of size k

Question: Print All k size subset of given array of size n

Algorithm:
Suppose array size is of length 5 ie A = {1,2,3,4,5};
and we need all the subsets of size k=3.

If we were supposed to find all the subsets then we would have taken all the binary representations of numbers from 1 to (2^5 - 1) and then according to the bits set, we would have chosen the corresponding number from Array A.

Now the idea is get the minimum number where all "k" lower bits are set.
In our case that would be = "00111" => 7 in decimal
Now find the next decimal number > 7 where 3 bits are set.
Keep on finding the next numbers till you hit "11100" = 28 since that is the largest binary number with 3 bits set of length 5.

Given an integer, method to find the next smallest number that have the same numbers of bits set:
1. Traverse from right to left, Once we have passed a 1, turn on the next 0.
ex: 101110 becomes 111110
2. Turn off the one that's just to the right side of that (where you switched on '0' to '1').
now 111110 becomes 110110.
3. Make the number as small as possible by rearranging all the 1's to be as far as right as possible.
ex: 110110 becomes 110011.

public class KSubSet {

	public static void main(String[] args) {
		int[] A = { 1, 2, 3, 4, 5 };
		int k = 3;
		int len = A.length;
		int result = 0;

		StringBuffer sb = new StringBuffer();
		int diff = len - k;

		for (int i = 1; i <= diff; i++) {
			sb.append('0');
		}
		for (int i = 1; i <= k; i++) {
			sb.append('1');
		}

		String binStr = sb.toString();
		String finalBinStr = sb.reverse().toString();
		int last = Integer.parseInt(finalBinStr, 2);
		// System.out.println("LAST:" + last);
		System.out.println("Subsets of size " + k + " are: ");
		printSubSet(A, binStr);
		result = Integer.parseInt(binStr, 2);
		while (result < last) {
			binStr = findNext(result, len);
			printSubSet(A, binStr);
			result = Integer.parseInt(binStr, 2);
		}
	}

	public static void printSubSet(int[] A, String binaryString) {
		int len = binaryString.length();
		for (int i = 0; i < len; i++) {
			if (binaryString.charAt(i) == '1') {
				System.out.print(A[i] + " ");
			}
		}
		System.out.println();
	}

	// finds the next smallest number with same number of k bits set.
	public static String findNext(int n, int k) {
		StringBuffer sbuff = new StringBuffer();

		int l = Integer.toBinaryString(n).length();
		if (l < k) {
			for (int i = 1; i <= (k - l); i++) {
				sbuff.append('0');
			}
		}
		char[] ch = (sbuff.toString() + Integer.toBinaryString(n))
				.toCharArray();
		int len = ch.length;
		boolean switched = false;
		int index = 0;
		for (int i = len - 1; i >= 0; i--) {
			if (ch[i] == '1') {
				for (int j = i - 1; j >= 0; j--) {
					if (ch[j] == '0') {
						ch[j] = '1';
						ch[j + 1] = '0';
						index = j + 1;
						// System.out.println("J:" + j + " J+1:" + (j+1));
						switched = true;
						break;
					}
				}
				if (switched) {
					break;
				}
			}
		}
		int i = index + 1;
		int j = len - 1;

		while (i < j) {
			if (ch[i] == '1' && ch[j] == '0') {
				ch[i] = '0';
				ch[j] = '1';
				++i;
				--j;
			}
			++i;
		}
		StringBuffer sb = new StringBuffer();
		for (i = 0; i < len; i++) {
			sb.append(ch[i]);
		}

		return sb.toString();
	}

}