Combination Sum

Given an array of distinct candidate numbers and a target, return all unique combinations where the chosen numbers sum to the target. Each candidate may be used unlimited times. Combinations can be returned in any order.

Function signature

func CombinationSum(candidates []int, target int) [][]int

Inputs / outputs

• candidates: distinct positive integers.
• target: positive integer target sum.
• Return: all unique combinations that sum to target.

Example

candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Constraints

• 1 <= len(candidates) <= 30
• 1 <= target <= 500

Core idea (near-solution)

Backtrack over candidates in non-decreasing order. Reusing the same index avoids permutation duplicates.

Invariant: path is a non-decreasing sequence of candidates whose sum is target - remain.

Algorithm (step-by-step)

1. (Optional) Sort candidates to enable pruning.
2. DFS dfs(start, remain):
   • If remain == 0, record a copy of path.
   • For each index i from start to end:
     • If sorted and candidates[i] > remain, break.
     • Choose candidates[i], recurse with dfs(i, remain - candidates[i]) (reuse allowed).
     • Backtrack.
3. Return all recorded combinations.

Correctness sketch

• Invariant: path is a non-decreasing sequence of candidates whose sum is target - remain.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

Trace (hand walkthrough)

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

Walk:
- take 2 -> remain 5; take 2 -> remain 3; take 3 -> [2,2,3]
- take 7 directly -> [7]

Pitfalls to avoid

• Using i+1 in recursion (would forbid reuse).
• Failing to copy path when adding to results.
• Producing duplicate permutations by resetting start to 0.

Complexity

• Time: exponential in the size of the search space.
• Extra space: O(target) recursion depth in the worst case.

Implementation notes (Go)

• Store results as [][]int and copy path with append([]int(nil), path...).
• Sorting allows early pruning and smaller search.