Minor changes
As @coderodde already stated, there is not much to improve, nonetheless a few minor things:
You can reduce the scope of the variables x
(which has always the same value as k prior entering the inner loop) and k
to the inner/outer loop.
for (int i = array.length - 1; i >= 0; --i)
can be written as for (int i = array.length; --i >= 0;)
.
Your inner loop starts at j = 1
but only uses j - 1
, you can start the loop at 0
to avoid the subtraction.
Depending on how null
s should be handled, you could use res[k++] = array[i].toString()
to throw a NPE if null
elements are present. If null
s are permitted, I would prefer that the string "null"
is added to the resulting array rather than a null
reference.
You could start k
and j
at -1
and use the (in theory) more efficient preincrement operator instead of the postincrement operator.
Possible implementation (not using preincrement for k
and j
as I think it makes the code more difficult to read):
public static String[] combinations(String[] array) {
String[] res = new String[-1 >>> -array.length];
for (int i = array.length, k = 0; --i >= 0;) {
String s = res[k] = array[i].toString();
for (int j = 0, x = k++; j < x;)
res[k++] = s + res[j++];
}
return res;
}
Alternative implementation
Your current implementation supports arrays with a maximum length of 30, you could provide a method #combination(String[] array, long index)
to support arrays with up to 64 elements (or a larger datatype than long
to support way larger input arrays).
public static String combination(String[] array, long index) {
// Could iterate twice to determine length (and coder) first
// to avoid resizing buffer (and could share the resulting
// byte array), kept this way for simplicity.
if (array.length > 64 || index == -1 || index + 1 >>> array.length != 0)
throw new IllegalArgumentException();
index = index + 1 << -array.length;
StringBuilder sb = new StringBuilder();
for (int i = -1; index != 0;) {
int nlz = numberOfLeadingZeros(index);
sb.append(array[i += nlz + 1]);
index = index << nlz << 1;
}
return sb.toString();
}