Crack the Backend

Problem Statement

Given an array of distinct positive integers candidates and a positive integer target, return all unique combinations of numbers from candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one chosen number is different.

We need to list all such combinations (not just the count). Backtracking (DFS) is the natural approach: at each step, choose a candidate and recurse with the remaining target, or skip to the next candidate.
To avoid duplicate combinations (e.g. [2,2,3] vs [2,3,2]), we iterate candidates in order and only consider candidates from the current index onward when we "take" a number.

Key Observations

Backtracking: We maintain a path (current combination) and remaining (target minus sum of path). From index i, we can either (1) take candidates[i] (add to path, reduce remaining, stay at i to allow reuse) or (2) skip candidates[i] (move to i+1). When remaining == 0, we have a valid combination — add a copy of path to the result. When remaining < 0 or we have exhausted candidates, backtrack.
Sorting candidates is optional but can help prune (stop when candidates[i] > remaining).
For counting combinations only, we could use DP: dp[t] = number of ways to make sum t; dp[t] += dp[t - c] for each c in candidates.

Approach

High-level: DFS/backtrack: at each call we have a start index and remaining target. Try adding candidates[i] for i >= start (so we can reuse), recurse with same i and remaining - candidates[i]; when remaining == 0, record the path. Then backtrack (remove from path) and try next index.

Steps:

Optionally sort candidates. Call dfs(candidates, target, 0, path, result).
In dfs(remaining, start): if remaining == 0, add copy of path to result and return. If remaining < 0 or start >= n, return. For i = start..n-1: if candidates[i] > remaining break (if sorted). path.add(candidates[i]), dfs(remaining - candidates[i], i), path.remove.
Return result.

Implementation

Java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    dfs(candidates, target, 0, new ArrayList<>(), result);
    return result;
}

void dfs(int[] c, int t, int start, List<Integer> path, List<List<Integer>> result) {

    if (t == 0) { result.add(new ArrayList<>(path)); return; }
    if (t < 0) {
        return;
    }

    for (int i = start; i < c.length; i++) {
        path.add(c[i]);
        dfs(c, t - c[i], i, path, result);
        path.remove(path.size() - 1);
    }
}

Test Cases

Example 1

Input

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

Expected

[[2,2,3],[7]]

Explanation

2+2+3=7 and 7=7.

Complexity Analysis

Time: O(2^target) in worst case.
Space: O(target) for recursion.

Follow-ups

Combination Sum II: each candidate used at most once; avoid duplicate combinations.