Problem #39: Combination Sum

Intuition & Strategy Breakdown

Use backtracking to explore candidate combinations. Since elements can be reused, recursively pass the current index when choosing an element until the sum equals target.

Python Solution

def combinationSum(candidates, target):
    res = []
    
    def dfs(i, cur, total):
        if total == target:
            res.append(cur.copy())
            return
        if i >= len(candidates) or total > target:
            return
        
        # Decision to include candidates[i]
        cur.append(candidates[i])
        dfs(i, cur, total + candidates[i])
        
        # Decision NOT to include candidates[i]
        cur.pop()
        dfs(i + 1, cur, total)
        
    dfs(0, [], 0)
    return res

Java Solution

class Solution {
    public List> combinationSum(int[] candidates, int target) {
        List> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }
    
    private void backtrack(int[] candidates, int target, int start, List current, List> res) {
        if (target == 0) {
            res.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                current.add(candidates[i]);
                backtrack(candidates, target - candidates[i], i, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
}