Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Backtracking

Guide 1 of 6 · Path 1 of 6

PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumbacktracking

Combination Sum

Problem (restated)

Distinct candidates; unlimited reuse. Find all unique combinations that sum to target.

Intuition

DFS with start index (order fixed → uniqueness). Reuse by calling dfs(i) after pick, not i+1.

Approaches

Reuse-allowed DFS

Tested only
Time O(n^(T/min))Space O(T/min)

Idea. dfs(start, remain): if 0 record; for i>=start if candidates[i] is at most remain take and dfs(i).

Walkthrough. candidates=[2,3,6,7], target=7 → [2,2,3] and [7].

Trade-offs. Unlike permutations, start index avoids order duplicates.

Solution
export function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remain: number) => {
    if (remain === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      const x = candidates[i]!;
      if (x > remain) continue;
      path.push(x);
      dfs(i, remain - x);
      path.pop();
    }
  };
  dfs(0, target);
  return res;
}

export function combinationSum(candidates: number[], target: number): number[][] {
  const res: number[][] = [];
  const path: number[] = [];
  const dfs = (start: number, remain: number) => {
    if (remain === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length; i++) {
      const x = candidates[i]!;
      if (x > remain) continue;
      path.push(x);
      dfs(i, remain - x);
      path.pop();
    }
  };
  dfs(0, target);
  return res;
}

Template connection

Backtracking with reuse.

Reflection