package com.thealgorithms.others;
/**
* Class for generating all subsequences of a given string.
*/
public final class ReturnSubsequence {
private ReturnSubsequence() {
}
/**
* Generates all subsequences of the given string.
*
* @param input The input string.
* @return An array of subsequences.
*/
public static String[] getSubsequences(String input) {
if (input.isEmpty()) {
return new String[] {""}; // Return array with an empty string if input is empty
}
// Recursively find subsequences of the substring (excluding the first character)
String[] smallerSubsequences = getSubsequences(input.substring(1));
// Create an array to hold the final subsequences, double the size of smallerSubsequences
String[] result = new String[2 * smallerSubsequences.length];
// Copy the smaller subsequences directly to the result array
System.arraycopy(smallerSubsequences, 0, result, 0, smallerSubsequences.length);
// Prepend the first character of the input string to each of the smaller subsequences
for (int i = 0; i < smallerSubsequences.length; i++) {
result[i + smallerSubsequences.length] = input.charAt(0) + smallerSubsequences[i];
}
return result;
}
}