40.combination-sum-ii.md

40. Combination Sum II

How to avoid duplicate combinations is the key:

• We sort the candidates so that we can search candidate in order.
• We can prevent duplicate combination via skiping searching duplicate candidate at the same search level.

https://leetcode.cn/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/225211/

private val results = mutableListOf<List<Int>>()

fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
    candidates.sort()
    dfs(candidates, 0, target, mutableListOf<Int>())
    return results
}

private fun dfs(candidates: IntArray, startIndex: Int, remaining: Int, combination: MutableList<Int>) {
    if (remaining == 0) {
        results.add(ArrayList<Int>(combination))
        return
    }
    
    for (i in startIndex until candidates.size) {
        // Duplicate candidate, we won't search (we search before already)
        if (i > startIndex && candidates[i] == candidates[i - 1]) continue
        val num = candidates[i]
        // Prune
        if (remaining - num < 0) break
        combination.add(num)
        dfs(candidates, i + 1, remaining - num, combination)
        combination.removeAt(combination.size - 1)
    }
}

• Time Complexity: O(2^n * n), O(2^n) for 2 choice for every candidate, and every candidate can have O(n) sub-candidates.
• Space Complexity: O(target) for dfs() recursive function call stack.