Find combinations for a target sum
Find every combination of distinct positive candidate values that sums to a target, allowing each candidate to be reused.
Course progress
Problem 97 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
candidates = [2, 3, 6, 7]; target = 7
Expected output
2+2+3, 7
What is happening?
Reusing 2 gives 2 + 2 + 3 = 7, and candidate 7 reaches the target alone. No other non-decreasing combination works.
Solution strategy
Build the right mental model
Choose candidates from the current index onward, subtract each choice from the remaining target, and backtrack after recursion.
Core concepts
backtracking · combinations
Complexity
Exponential time in the target, with O(target / smallest candidate) call-stack space.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for combination-sum
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void FindCombinations(int[] candidates, int start, int remaining,
List<int> current, List<string> results)
{
if (remaining == 0)
{
results.Add(string.Join("+", current));
return;
}
for (int i = start; i < candidates.Length && candidates[i] <= remaining; i++)
{
current.Add(candidates[i]);
FindCombinations(candidates, i, remaining - candidates[i], current, results);
current.RemoveAt(current.Count - 1);
}
}
static void Main()
{
int[] candidates = { 2, 3, 6, 7 };
var results = new List<string>();
FindCombinations(candidates, 0, 7, new List<int>(), results);
Console.WriteLine(string.Join(", ", results));
}
}Knowledge check
Questions students often ask
What is the main idea behind find combinations for a target sum?
Choose candidates from the current index onward, subtract each choice from the remaining target, and backtrack after recursion.
What is the time and space complexity of this solution?
Exponential time in the target, with O(target / smallest candidate) call-stack space.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.