Print All String Combinations Using Recursive function

Print all the possible combinations of a given String using Recursive function in Java

Here we’re using two recursive functions given the string is “abcd”:

1. substring is responsible for generating all possible substrings of given string in forward direction i.e. a, ab, abc, abcd, b, bc, bcd, c, cd, and d
2. permutation is responsible for generating all possible permutation of substring generated by substring() method of same length for e.g. possible permutation of abc is abc, acb, bac, bca, cab, and cba

public class PrintAllCombinationOfString {

	public static void main(String[] args) {
		String s = "abcd";
		for (int i = 0; i < s.length(); i++) {
			substring(s, "", i);
		}
	}
	
	public static void substring(String content, String part, int index) {
		if (index >= content.length()) {
			return;
		}
		String sub = part + content.charAt(index);

		permutation("", sub);

		substring(content, sub, index + 1);
	}

	private static void permutation(String prefix, String str) {
		int n = str.length();
		if (n == 0) {
			System.out.println(prefix);
		} else {
			for (int i = 0; i < n; i++) {
				permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
			}
		}
	}
}

Output
a
ab
ba
abc
acb
bac
bca
cab
cba
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
b
bc
cb
bcd
bdc
cbd
cdb
dbc
dcb
c
cd
dc
d

How It Works

substring() walks each starting index i of the input and extends the substring one character at a time — a, ab, abc, abcd for i = 0, then b, bc, bcd for i = 1, and so on — so it produces every contiguous substring of the original string. Note the terminology: mathematically these are combinations only in the sense of “which contiguous slice”, not full subsequence combinations (e.g. ac skipping b is never generated). For a string of length n, the number of contiguous substrings is n(n+1)/2 — for "abcd" (n = 4) that’s 4·5/2 = 10, matching the 10 substrings listed in the comment above the code.

For each substring, permutation() then does a classic recursive permutation: pick each remaining character as the next one in prefix, and recurse on what’s left (str.substring(0, i) + str.substring(i + 1, n) removes the chosen character and reassembles the rest). A substring of length k has k! permutations, and that’s exactly what gets printed for it.

Complexity

Total lines printed = sum over every substring of (length)!. Since there are (n - k + 1) substrings of length k, that total is:

Σ (n - k + 1) · k!   for k = 1 to n

For n = 4: 4·1! + 3·2! + 2·3! + 1·4! = 4 + 6 + 12 + 24 = 46 — which is exactly the 46 lines in the output above. The k = n term alone contributes n!, and it dominates every smaller term combined, so the overall time (and output size) is 𝘖(n · n!) — the extra factor of n accounts for the 𝘖(n) work of building and printing each permutation string. Recursion depth for permutation() never exceeds n, so space complexity (excluding the output itself) is 𝘖(n).

Because String is immutable in Java, every prefix + str.charAt(i) and every substring(...) call allocates a new String object rather than mutating one in place. That’s fine at the small sizes this kind of exercise is normally run at, but it means the constant factor is heavier than a version built around a mutable char[] — worth keeping in mind if you ever need to run this on strings longer than a handful of characters, since both time and allocations grow factorially.

Edge Case: Duplicate Characters

The algorithm treats characters purely by position, not by value, so a repeated character produces duplicate output. Running the same code on "aab" instead of "abcd":

String s = "aab";
for (int i = 0; i < s.length(); i++) {
    substring(s, "", i);
}

Output
a
aa
aa
aab
aba
aab
aba
baa
baa
a
ab
ba
b

"aa" and both 3-letter permutations ("aab", "aba") each appear twice — once for every arrangement of the positions holding the two 'a' characters, even though swapping two equal characters produces an identical string. If duplicate output is a problem, de-duplicate with a Set<String> (trading memory for uniqueness), or skip a swap in the permutation step whenever the character being placed already appeared earlier at that same recursion depth.