Combination Sum

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example: Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3], [7]]

Interactive Visualization

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {    val result = mutableListOf<List<Int>>()    fun backtrack(start: Int, current: MutableList<Int>, remaining: Int) {        // enter backtrack        if (remaining == 0) {            result.add(current.toList())            return        }        for (i in start until candidates.size) {            if (candidates[i] > remaining)                continue            current.add(candidates[i])            backtrack(i, current, remaining - candidates[i])            current.removeAt(current.size - 1)        }    } // end backtrack    backtrack(0, mutableListOf(), target)    return result}

def combinationSum(candidates, target):    result = []    def backtrack(start, current, remaining):        # enter backtrack        if remaining == 0:            result.append(current[:])            return        for i in range(start, len(candidates)):            if candidates[i] > remaining:                continue            current.append(candidates[i])            backtrack(i, current, remaining - candidates[i])            current.pop()    # end backtrack    backtrack(0, [], target)    return result

How It Works

Backtracking Approach

The Combination Sum problem is solved using backtracking, which systematically explores all possible combinations by making choices and undoing them (backtracking) when they don't lead to a solution.

Key Concepts

• Decision Tree: Each node represents a decision point where we choose whether to include a candidate number in our combination.
• Running Sum: At each node, we track the current sum of chosen numbers.
• Remaining Target: We calculate how much more we need to reach the target (target - current sum).
• Pruning: When a candidate exceeds the remaining target, we skip it (prune that branch) since it cannot lead to a valid solution.
• Reusability: Since we can reuse numbers, when we choose a number at index i, the next recursive call also starts from i (not i+1).

Algorithm Steps

1. Base Case: If remaining target equals 0, we've found a valid combination - add it to results.
2. Iterate: For each candidate starting from the current index:
   • If candidate > remaining, skip it (pruning)
   • Add candidate to current combination
   • Recursively explore with updated remaining target
   • Backtrack: remove the candidate and try the next one
3. Return: After exploring all possibilities, return all valid combinations found.

Time & Space Complexity

• Time Complexity: O(N^(T/M)), where N is the number of candidates, T is the target, and M is the minimal value among candidates. In the worst case, we might explore many combinations.
• Space Complexity: O(T/M) for the recursion depth (maximum depth of the decision tree).

Visualization Features

• Decision Tree: Shows the complete exploration tree with nodes colored based on their state (exploring, valid, pruned).
• Current Combination: Displays the numbers currently in the combination being built.
• Pruning Visualization: Red nodes and crossed branches show where pruning occurs.
• Valid Results: Green boxes show all valid combinations found so far.