// Recursive
fun getMaxProfitItemsRecursive(weights: IntArray, profits: IntArray, capacity: Int): IntArray {
    // edge case
    if (capacity == 0 || weights.isEmpty() || profits.isEmpty() || weights.size != profits.size) {
        return intArrayOf()
    }

    val selectedItems = ArrayList<Int>()

    val maxProfit = helper(weights, profits, capacity, 0, selectedItems)

    println("maxProfit== $maxProfit")

    return selectedItems.toIntArray()
}

private fun helper(weights: IntArray, profits: IntArray, capacity: Int, current: Int, selected: ArrayList<Int>): Int {
    // Base case
    if (capacity == 0 || current >= weights.size) {
        return 0
    }

    // select current item
    var selectedProfit = 0
    if (weights[current] <= capacity) {
        selectedProfit = profits[current] + helper(weights, profits, capacity - weights[current], current + 1, selected)
    }

    // skip current item
    val unselectedProfit = helper(weights, profits, capacity, current + 1, selected)

    return max(selectedProfit, unselectedProfit)
}