Combination Sum [Medium] — Backtracking with Pruning

Problem Statement

Given candidates (distinct) and a target, find all unique combinations of candidates where the chosen numbers sum to target. Each number may be used unlimited times.

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

Intuition

DFS/backtracking: at each position, try all candidates >= current index, reduce target, and recurse. Backtrack when target == 0 (add to result) or < 0 (prune).

Solutions

C++

void dfs(vector<int>& c, int target, int start, vector<int>& cur, vector<vector<int>>& res) {
    if (target == 0) { res.push_back(cur); return; }
    for (int i = start; i < (int)c.size() && c[i] <= target; i++) {
        cur.push_back(c[i]);
        dfs(c, target - c[i], i, cur, res);
        cur.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res; vector<int> cur;
    dfs(candidates, target, 0, cur, res);
    return res;
}

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(candidates);
    dfs(candidates, target, 0, new ArrayList<>(), res);
    return res;
}
void dfs(int[] c, int rem, int start, List<Integer> cur, List<List<Integer>> res) {
    if (rem == 0) { res.add(new ArrayList<>(cur)); return; }
    for (int i = start; i < c.length && c[i] <= rem; i++) {
        cur.add(c[i]); dfs(c, rem - c[i], i, cur, res); cur.remove(cur.size()-1);
    }
}

JavaScript

var combinationSum = function(candidates, target) {
    candidates.sort((a,b) => a-b);
    const res = [];
    function dfs(rem, start, cur) {
        if (rem === 0) { res.push([...cur]); return; }
        for (let i = start; i < candidates.length && candidates[i] <= rem; i++) {
            cur.push(candidates[i]);
            dfs(rem - candidates[i], i, cur);
            cur.pop();
        }
    }
    dfs(target, 0, []);
    return res;
};

Python

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    res = []
    def dfs(rem, start, path):
        if rem == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > rem:
                break
            path.append(candidates[i])
            dfs(rem - candidates[i], i, path)
            path.pop()
    dfs(target, 0, [])
    return res

Complexity

Time: O(n^(t/m)) where t=target, m=min candidate
Space: O(t/m) recursion depth