K Sum

Given a set S of n integers and an integer T, give an algorithm to test whether k of the integers in S add up to T.

IDEA:

For target=21, k=3 i.e. 21/3 and array:

! 5 ! 6 ! 8 ! 10 ! 12 !

<------- 21/3 ------>

^ <--- 16/2 --->

   ^ <---  10/1 --->

package algorithmdesignmanualbook.sorting

import kotlin.test.assertTrue

/**
 * Given a set S of n integers and an integer T,
 * give an algorithm to test whether k of the integers in S add up to T.
 *
 * [Another way](https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/)
 *
 * ### IDEA:
 *
 * ```
 * For target=21, k=3 i.e. 21/3 and array:
 *
 * ! 5 ! 6 ! 8 ! 10 ! 12 !
 *
 *  <------- 21/3 ------>
 *
 *   ^ <---   16/2    --->
 *
 *       ^ <---  10/1 --->
 * ```
 */
class KSum(_input: Array<Int>, private val target: Int, private val k: Int) {
    val result = mutableListOf<MutableList<Int>>()

    // Sort it first
    val array: Array<Int> = _input.sortedArray()

    fun execute(): List<List<Int>> {
        for (i in 0..array.lastIndex) {
            val temp = mutableListOf<Int>()
            kSumHelper(k, target, i, temp)
        }
        println(result)
        return result
    }

    private fun kSumHelper(
        remainingKCount: Int,
        remainingSum: Int,
        currentIndex: Int,
        temp: MutableList<Int>
    ) {
        // array out of bound
        if (currentIndex > array.lastIndex) {
            return
        }
        // Only 1 item remains
        if (remainingKCount == 1) {
            // When you have 1 item remaining, just find if from current index to end, there exists an item == [remainingSum]
            if (array.sliceArray(currentIndex..array.lastIndex).contains(remainingSum)) {
                temp.add(remainingSum)
                // Since sum( [temp] + remainingSum ) == target
                result.add(temp)
                return
            }
        }
        temp.add(array[currentIndex])
        kSumHelper(
            remainingKCount = remainingKCount - 1, // Since you consider current element, then decrease the [remainingKCount]
            remainingSum = remainingSum - array[currentIndex], // Remove it from sum
            currentIndex = currentIndex + 1,
            temp = temp
        )
    }
}

fun main() {
    val input = arrayOf(-4, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8)
    run {
        KSum(input, 6, 3).execute().forEach {
            assertTrue {
                it.sum() == 6 && it.size == 3
            }
        }
    }

    run {
        KSum(input, 8, 2).execute().forEach {
            assertTrue {
                it.sum() == 8 && it.size == 2
            }
        }
    }

    run {
        KSum(input, 11, 3).execute().forEach {
            assertTrue {
                it.sum() == 11 && it.size == 3
            }
        }
    }
}

View on GitHub

Updated on 2021-02-20

IDEA:​

IDEA: