Combination of String

A Combination of string could be described as the collection of the characters which it contains.

Unlike permutations, two combinations are considered to be the same if they contain the same characters, but may be in a different order. Give an algorithm that prints all possible combinations of the characters in a string. For example, “ac” and “ab” are different combinations from the input string “abc”, but “ab” is the same as “ba”.

The solution is achieved by generating n!/r! (n – r)! strings, each of length between 1 and n where n is the length of the given input string.

As, mathematically, to find r combinations of the string with n characters in given by nCr.

So, if finding all the possible combination of the string we then have to go for
nC0 + nC1 + nC2 + ... + nCn

Also, from solving the above additon we have

nC0 + nC1 + nC2 + ... + nCn = 2ⁿ

That means the total number of combinations of the string would be 2ⁿ.

With this in mind you can represent each of the character within the string as a binary equivalent from 0 to 2ⁿ (exculding 2ⁿ, as we consider 0, as net there are 2ⁿ combinations).

For Example:

Take a String s = "ABC"

here n = 3,

So number of combinations are from zero (0) to 2³ (ie, 8)

number	binary equivalent	String
0	000	""
1	001	"C"
2	010	"B"
3	011	"BC"
4	100	"A"
5	101	"AC"
6	110	"AB"
7	111	"ABC"

Show me the Code

Here is the Code to do this.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class CombinationOfString {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        System.out.println("Enter a String");
        final String s = sc.next();
        final List<String> combinations = new ArrayList<>();

        findCombinations(s, 0, new StringBuilder(""), combinations);

        System.out.println(combinations.stream().collect(Collectors.joining(" ")));
    }

    private static void findCombinations(String s, int startIndex, StringBuilder runner, List<String> combinations) {
        for (int i = startIndex; i < s.length(); i++) {
            // Add Character to end
            runner.append(s.charAt(i));

            // Save the combination
            combinations.add(runner.toString());

            // Take current info of runner and string and start from the next index
            findCombinations(s, i+1, runner, combinations);

            // Remove Character from the end
            runner.setLength(runner.length() - 1);
        }
    }
}