package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

///**
// * Class generates all subsequences for a given list of elements using backtracking
// */
//public final class SubsequenceFinder {
//    private SubsequenceFinder() {
//    }
//
//    /**
//     * 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
//     */
//    public static <T> List<List<T>> generateAll(List<T> sequence) {
//        List<List<T>> allSubSequences = new ArrayList<>();
//        if (sequence.isEmpty()) {
//            allSubSequences.add(new ArrayList<>());
//            return allSubSequences;
//        }
//        List<T> currentSubsequence = new ArrayList<>();
//        backtrack(sequence, currentSubsequence, 0, allSubSequences);
//        return allSubSequences;
//    }
//
//    /**
//     * 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
//     */
//    private static <T> void backtrack(List<T> sequence, List<T> currentSubsequence, final int index, List<List<T>> allSubSequences) {
//        assert index <= sequence.size();
//        if (index == sequence.size()) {
//            allSubSequences.add(new ArrayList<>(currentSubsequence));
//            return;
//        }
//
//        backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
//        currentSubsequence.add(sequence.get(index));
//        backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
//        currentSubsequence.removeLast();
//    }
//}

/**
 * 类使用回溯算法为给定元素列表生成所有子序列
 */
public final class SubsequenceFinder {
    private SubsequenceFinder() {
    }

    /**
     * 使用回溯算法找出给定列表的所有子序列
     *
     * @param sequence 我们需要基于此生成所有子序列的元素列表
     * @param <T> 数组中元素的类型
     * @return 所有子序列的列表
     */
    public static <T> List<List<T>> generateAll(List<T> sequence) {
        List<List<T>> allSubSequences = new ArrayList<>();
        if (sequence.isEmpty()) {
            allSubSequences.add(new ArrayList<>());
            return allSubSequences;
        }
        List<T> currentSubsequence = new ArrayList<>();
        backtrack(sequence, currentSubsequence, 0, allSubSequences);
        return allSubSequences;
    }

    /**
     * 遍历每个状态的分支
     * 我们知道每个状态正好有两个分支
     * 当到达给定序列的末尾时终止
     *
     * @param sequence 所有元素
     * @param currentSubsequence 当前子序列
     * @param index 当前索引
     * @param allSubSequences 包含所有序列的列表
     * @param <T> 我们生成的元素的类型
     */
    private static <T> void backtrack(List<T> sequence, List<T> currentSubsequence, final int index, List<List<T>> allSubSequences) {
        assert index <= sequence.size();
        if (index == sequence.size()) {
            allSubSequences.add(new LinkedList<>(currentSubsequence));
            return;
        }

        backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
        currentSubsequence.add(sequence.get(index));
        backtrack(sequence, currentSubsequence, index + 1, allSubSequences);
        currentSubsequence.remove(currentSubsequence.size() - 1);
    }
}

