package aoc

func CombinationsWithReplacement[T any](input []T, n int) [][]T {
	var helper func(int, int, []T)
	result := [][]T{}

	helper = func(start int, remaining int, current []T) {
		if remaining == 0 {
			combination := make([]T, len(current))
			copy(combination, current)
			result = append(result, combination)
			return
		}
		for i := start; i < len(input); i++ {
			helper(i, remaining-1, append(current, input[i]))
		}
	}
	helper(0, n, []T{})
	return result
}