77.combinations.md

77. Combinations

val results = mutableListOf<MutableList<Int>>()

fun combine(n: Int, k: Int): List<List<Int>> {
    val choices = mutableListOf<Int>()
    dfs(1, n, k, mutableListOf())
    return results
}

private fun dfs(start: Int, n: Int, k: Int, result: MutableList<Int>) {
    if (k == 0) {
        // Add to new collection (deep copy), this is required because
        // we manipulate the same collections during DFS.
        results.add(ArrayList<Int>(result))
        return
    }

    for (i in start..n) {
        // Pruning
        if (n - i + 1 < k) break

        result.add(i)

        // Go to next choices
        dfs(i + 1, n, k - 1, result)

        // Backtracking, remove the last item we added for next choices to rollback to previous state.
        result.removeAt(result.size - 1)
    }
}

For backtracking, we can use queue to store the result of searching path.

TODO: Confirm the following complexity and make sure understand.

• Time Complexity: O(m * k), where m is the number of n choose k.
• Space Complexity: O(k + n)