Find all possible Combinations of String in Java

In this post, you will learn how to write a program to find all possible combinations of String in Java. In the context of computer science and programming, “string combinations” refer to the various ways in which you can arrange or select characters from a given string. A combination is a selection of items from a larger set, where the order of the selected items doesn’t matter.

For example, let’s consider the string “ABC”. The combinations of this string would include all possible ways of selecting characters from the string without considering the order. Here are the combinations for the string “ABC”:

1. “A”
2. “B”
3. “C”
4. “AB”
5. “AC”
6. “BC”
7. “ABC”

Combinations of String Program in Java

Here’s a Java program that generates all possible combinations of characters in a given string,

package com.javacodepoint.string;

import java.util.ArrayList;
import java.util.List;
/*
 * Find the String Combinations Example
 */
public class StringCombinations {

	public static List<String> generateCombinations(String input) {
		List<String> combinations = new ArrayList<>();
		backtrack("", input, combinations);
		return combinations;
	}

	private static void backtrack(String current, String remaining, List<String> combinations) {
		// Base case: When there are no more characters remaining,
		// add the current combination to the list
		if (remaining.length() == 0) {
			combinations.add(current);
			return;
		}

		// include the first character of remaining in the current combination
		backtrack(current + remaining.charAt(0), remaining.substring(1), combinations);

		// exclude the first character of remaining from the current combination
		backtrack(current, remaining.substring(1), combinations);
	}

	public static void main(String[] args) {
		String input = "ABC";
		List<String> combinations = generateCombinations(input);

		System.out.println("Combinations of '" + input + "':");
		for (String combination : combinations) {
			System.out.println(combination);
		}
	}
}

OUTPUT:

Combinations of ‘ABC’:
ABC
AB
AC
A
BC
B
C

Explanation of the program:

1. generateCombinations method:
   • This method initializes an empty list combinations to store the generated combinations.
   • It then calls the private backtrack method to start generating combinations.
2. backtrack method (a recursive method):
   • This method takes three parameters: current (current combination being formed), remaining (remaining characters to be considered), and combinations (list to store generated combinations).
   • The base case checks if there are no more characters remaining. If so, the current combination is added to the list.
   • The method then performs two recursive calls:
     • One includes the first character of remaining in the current combination and removes it from remaining.
     • The other call excludes the first character of remaining from the current combination.
   • This creates a binary tree-like structure of recursive calls, exploring all possible combinations.
3. main method:
   • In the main method, we specify the input string (e.g., “ABC”).
   • We call the generateCombinations method to generate all combinations.
   • We then iterate through the list of combinations and print each one.

Conclusion

The concept of string combinations in computer science involves exploring the various ways characters can be selected from a given string without considering their order. Combinations provide a fundamental building block for solving problems and implementing algorithms across different domains. By generating combinations, programmers can tackle challenges such as permutations, puzzles, and cryptography.

In programming, you might encounter scenarios where you need to generate or manipulate combinations of characters to achieve a specific task or solve a particular problem. The above program in Java demonstrates how you can generate all possible combinations of characters from a given string using a backtracking approach.

See also: String Permutations Program in Java