SubsequenceFinder.java

packagecom.thealgorithms.backtracking;

importjava.util.ArrayList;
importjava.util.List;

/**
 * Class generates all subsequences for a given list of elements using backtracking
 */
publicfinalclassSubsequenceFinder {
privateSubsequenceFinder() {
 }

/**
 * Find all subsequences of given list using backtracking
 *
 * @param sequence a list of items on the basis of which we need to generate all subsequences
 * @param <T> the type of elements in the array
 * @return a list of all subsequences
 */
publicstatic <T> List<List<T>> generateAll(List<T> sequence) {
List<List<T>> allSubSequences = newArrayList<>();
if (sequence.isEmpty()) {
allSubSequences.add(newArrayList<>());
returnallSubSequences;
 }
List<T> currentSubsequence = newArrayList<>();
backtrack(sequence, currentSubsequence, 0, allSubSequences);
returnallSubSequences;
 }

/**
 * Iterate through each branch of states
 * We know that each state has exactly two branching
 * It terminates when it reaches the end of the given sequence
 *
 * @param sequence all elements
 * @param currentSubsequence current subsequence
 * @param index current index
 * @param allSubSequences contains all sequences
 * @param <T> the type of elements which we generate
 */
privatestatic <T> voidbacktrack(List<T> sequence, List<T> currentSubsequence, finalintindex, List<List<T>> allSubSequences) {
assertindex <= sequence.size();
if (index == sequence.size()) {
allSubSequences.add(newArrayList<>(currentSubsequence));
return;
 }

backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
currentSubsequence.add(sequence.get(index));
backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
currentSubsequence.removeLast();
 }
}