user2000189 user2000189 - 1 month ago 5x
Java Question

Form 2^n combination string

From a given string, to form different set of combination by considering the formula 2^n (2 power n).

For example consider the below example string (AA%0%0%). Where "%" is optional value, hence "%" can be added in string combination or can be removed from string combination, hence posibility of different string combinations as below.

Example String:
AA%0%0% {% index positions are [2,4,6]}

Different possible combination for the example string : (2^n, where n=3 (because "%" count is 3) equals 2^3 = 8 combinations)

For easy understanding, i am replacing "%" with "*" in below combination.

1. AA*0*0* [no % omitted]
2. AA*0*0 [index 6 % omitted]
3. AA*00* [index 4 % omitted]
4. AA0*0* [index 2 % omitted]
5. AA*00 [index 4,6 % omitted]
6. AA0*0 [index 2,6 % omitted]
7. AA00* [index 2,4 % omitted]
8. AA00 [index 2,4,6 % omitted]

Now the question is, number of "%" string will vary according to user input, hence, each time to form this combination, i want to write a program in java, which will automatically for this combination according to 2^n formula. Is there any already existing algorithm available to do so? kindly suggest.


For better understanding, i am giving different index which, can be formed from 3 count (2^3 = 8). This depends on index position, for example, % index are as 2,4,6 means

  1. [2]

  2. [4]

  3. [6]

  4. [2,4]

  5. [2,6]

  6. [4,6]

  7. [2,4,6]

  8. [No index (%) removed all characters available]


You can write a recursive implementation of this. The idea is to check in the provided string if the character at index i (which you can pass as paramter to the function) is % or not, if it is, then take two actions:

  • Make a recursive call by not omitting the character at index i (You need to make this call anyway, in both cases, i.e. whether the character at i is % or not)
  • Make a recursive call by omitting the character at index i (which is %, which we have checked)

And when i reaches at the end of the string, you've got yourself a combination. (Since you've done this many recursive calls, so you'll find all of the combinations)

Following, I'll implement using the above idea:

public static void allCombinations(String s, int i){
    if (i < s.length()){
        // Make a recursive call without removing the character
        allCombinations(s, i + 1);

        if (s.charAt(i) == '%'){
            // Remove character at index i and make a recursive call with new string
            String temp = s.substring(0, i) + s.substring(i + 1);
            allCombinations(temp, i);

        // print the combination found.

and call this recursive implementation by passing 0 as the starting index (because you need to start from 0) like this: allCombinations("AA%0%0%", 0);


here, you can find the implementation tested with the provided string (AA%0%0%) on ideone