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

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;

///**
// * Finds all permutations of given array
// * @author Alan Piao (<a href="https://github.com/cpiao3">git-Alan Piao</a>)
// */
//public final class Combination {
//    private Combination() {
//    }
//
//    private static int length;
//
//    /**
//     * Find all combinations of given array using backtracking
//     * @param arr the array.
//     * @param n length of combination
//     * @param <T> the type of elements in the array.
//     * @return a list of all combinations of length n. If n == 0, return null.
//     */
//    public static <T> List<TreeSet<T>> combination(T[] arr, int n) {
//        if (n == 0) {
//            return null;
//        }
//        length = n;
//        T[] array = arr.clone();
//        Arrays.sort(array);
//        List<TreeSet<T>> result = new LinkedList<>();
//        backtracking(array, 0, new TreeSet<T>(), result);
//        return result;
//    }
//
//    /**
//     * Backtrack all possible combinations of a given array
//     * @param arr the array.
//     * @param index the starting index.
//     * @param currSet set that tracks current combination
//     * @param result the list contains all combination.
//     * @param <T> the type of elements in the array.
//     */
//    private static <T> void backtracking(T[] arr, int index, TreeSet<T> currSet, List<TreeSet<T>> result) {
//        if (index + length - currSet.size() > arr.length) {
//            return;
//        }
//        if (length - 1 == currSet.size()) {
//            for (int i = index; i < arr.length; i++) {
//                currSet.add(arr[i]);
//                result.add((TreeSet<T>) currSet.clone());
//                currSet.remove(arr[i]);
//            }
//        }
//        for (int i = index; i < arr.length; i++) {
//            currSet.add(arr[i]);
//            backtracking(arr, i + 1, currSet, result);
//            currSet.remove(arr[i]);
//        }
//    }
//}

/**
 * 查找给定数组的所有排列组合
 * @author Alan Piao (<a href="https://github.com/cpiao3">git-Alan Piao</a>)
 */
public final class Combination {
    private Combination() {
    }

    private static int length;

    /**
     * 使用回溯法找出给定数组的所有组合
     * @param arr 数组
     * @param n 组合的长度
     * @param <T> 数组中元素的类型
     * @return 长度为n的所有组合的列表。如果n为0，则返回null。
     */
    public static <T> List<TreeSet<T>> combination(T[] arr, int n) {
        if (n == 0) {
            return null;
        }
        length = n;
        T[] array = arr.clone();
        Arrays.sort(array);
        List<TreeSet<T>> result = new LinkedList<>();
        backtracking(array, 0, new TreeSet<T>(), result);
        return result;
    }

    /**
     * 回溯给定数组的所有可能组合
     * @param arr 数组
     * @param index 起始索引
     * @param currSet 跟踪当前组合的集合
     * @param result 包含所有组合的列表
     * @param <T> 数组中元素的类型
     */
    private static <T> void backtracking(T[] arr, int index, TreeSet<T> currSet, List<TreeSet<T>> result) {
        if (index + length - currSet.size() > arr.length) {
            return;
        }
        if (length - 1 == currSet.size()) {
            for (int i = index; i < arr.length; i++) {
                currSet.add(arr[i]);
                result.add((TreeSet<T>) currSet.clone());
                currSet.remove(arr[i]);
            }
        }
        for (int i = index; i < arr.length; i++) {
            currSet.add(arr[i]);
            backtracking(arr, i + 1, currSet, result);
            currSet.remove(arr[i]);
        }
    }
}
