// https://leetcode.com/problems/combination-sum
fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    return mutableListOf<List<Int>>().also {
        buildCombinations(candidates, startIndex = 0, target = target, combination = mutableListOf(), combinations = it)
    }
}

private fun buildCombinations(
    candidates: IntArray,
    startIndex: Int,
    target: Int,
    combination: MutableList<Int>,
    combinations: MutableList<List<Int>>
) {
    if (target == 0) {
        combinations.add(combination.toList())
        return
    }
    for (index in startIndex..candidates.lastIndex) {
        val candidate = candidates[index]
        if (candidate <= target) {
            combination.add(candidate)
            buildCombinations(
                candidates = candidates,
                startIndex = index,
                target = target - candidate,
                combination = combination,
                combinations = combinations
            )
            combination.removeLast()
        }
    }
}

// https://leetcode.com/problems/combination-sum
fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    return mutableListOf<List<Int>>().also {
        buildCombinations(candidates, startIndex = 0, target = target, combination = mutableListOf(), combinations = it)
    }
}

private fun buildCombinations(
    candidates: IntArray,
    startIndex: Int,
    target: Int,
    combination: MutableList<Int>,
    combinations: MutableList<List<Int>>
) {
    if (target == 0) {
        combinations.add(combination.toList())
        return
    }
    for (index in startIndex..candidates.lastIndex) {
        val candidate = candidates[index]
        if (candidate <= target) {
            combination.add(candidate)
            buildCombinations(
                candidates = candidates,
                startIndex = index,
                target = target - candidate,
                combination = combination,
                combinations = combinations
            )
            combination.removeLast()
        }
    }
}
