class Main {
static void string_recurse(String active,String rest) {
if (rest.length() == 0) {
System.out.println(active);
} else {
string_recurse(active + rest.charAt(0), rest.substring(1, rest.length()));
string_recurse(active, rest.substring(1, rest.length()));
}
}
static void string_iterative(String s) {
int n = s.length();
for (int mask = (1 << n) - 1; mask >= 0; mask--) {
String temp = "";
for (int pos = 0; pos < n; pos++)
if (((1 << (n - 1 - pos)) & mask) != 0)
temp += s.charAt(pos);
System.out.println(temp);
}
}
public static void main(String[] args) {
String s = "abcd";
string_recurse("", s);
string_iterative(s);
}
}
Note: If you know that your string's length never goes over 32
use this iterative method. If you know that the string's length goes over 32
but is bounded by 64
define mask
as long
. If the length can be more than 64
stick with the original recursive method.
The idea of this iterative method is to map every character of the string to either 1
or 0
. 1
means that the corresponding character takes part in the current sub-word and 0
means the opposite. So to loop over all "subset words" we just need to loop from 00..0 (n bits)
to 11..1(n bits)
. This can be done just by looping over the integer range [0
, 2^n - 1
] and by using the binary representation of the numbers. Note that in the given example those numbers are looped over in reverse fashion in order for the iterative function to be consistent with the recursive one.