eric.liu.developer
BAN USERIf you want to avoid recursion, you can loop through the 2 to the power of (array.length -1) cases. The following code is written in java.
public <E> void findCombination(E[] array) {
int gapNumber = array.length - 1;
boolean[] gaps = new boolean[gapNumber];
for (int i = 0; i < Math.pow(2, gapNumber); i++) {
for (int gapIndex = 0; gapIndex < gaps.length; gapIndex++) {
//reset value
gaps[gapIndex] = false;
}
for (int gapIndex = 0; gapIndex < gapNumber; gapIndex++) {
if (getBit(i, gapIndex) > 0) {
gaps[gapIndex] = true;
}
}
printCombination(array, gaps);
}
}
private <E> void printCombination(E[] array, boolean[] gaps) {
System.out.print("(");
for (int i = 0; i < array.length; i++) {
if (i < gaps.length && gaps[i] == true) {
System.out.print(array[i]);
System.out.print(")(");
} else {
System.out.print(array[i]);
}
}
System.out.print(")\n");
}
public int getBit(int n, int k) {
return (n >> k) & 1;
}
@Test
public void testPrintCombination() {
Integer[] data = {1, 2, 3, 4};
findCombination(data);
}
- eric.liu.developer July 06, 2016
The best runtime complexity we can achieve is n*lg(n), the following code is written in java, using a binary search to find the biggest 0 index in a row.
}
- eric.liu.developer July 07, 2016