Problem Statement:
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
Approach:
- Use
backtrackingto explore all possible combinations of numbers that sum up to the target. - Start from an index (start) to avoid reusing previous elements in the
same path(but allow reuse of the current one). - At each step:
- If
remainingSum === 0, store the current path (valid combination). - If
remainingSum <, 0, stop exploring further. - Otherwise, try each number starting from start, include it in the path, and recurse with reduced sum.
- If
Backtrack(remove last element) to explore other possibilities.
Dry Run
Input: arr = [2, 3, 6, 7], target = 7
Step 0: Start Function combinationSum([2, 3, 6, 7], 7)
Initialize:
result = []
path = []
Call backtrack(7, [], 0)
Loop i = 0 → arr[0] = 2
path.push(2) → path = [2]
Call backtrack(5, [2], 0)
Loop i = 0 → arr[0] = 2
path.push(2) → path = [2, 2]
Call backtrack(3, [2, 2], 0)
Loop i = 0 → arr[0] = 2
path.push(2) → path = [2, 2, 2]
Call backtrack(1, [2, 2, 2], 0)
remainingSum > 0 but next choice will exceed → return
path.pop() → path = [2, 2]
Loop i = 1 → arr[1] = 3
path.push(3) → path = [2, 2, 3]
Call backtrack(0, [2, 2, 3], 1)
remainingSum == 0 → result.push([2, 2, 3])
path.pop() → path = [2, 2]
Loop ends
path.pop() → path = [2]
Loop i = 1 → arr[1] = 3
path.push(3) → path = [2, 3]
Call backtrack(2, [2, 3], 1)
further exploration doesn’t hit 0 → backtrack
path.pop() → path = [2]
Loop i = 2 → arr[2] = 6
path.push(6) → path = [2, 6]
Call backtrack(-1, [2, 6], 2)
remainingSum < 0 → return
path.pop() → path = [2]
Loop i = 3 → arr[3] = 7
path.push(7) → path = [2, 7]
Call backtrack(-2, [2, 7], 3)
remainingSum < 0 → return
path.pop() → path = [2]
Loop ends
path.pop() → path = []
Loop i = 1 → arr[1] = 3
path.push(3) → path = [3]
Call backtrack(4, [3], 1)
Loop i = 1 → arr[1] = 3
path.push(3) → path = [3, 3]
Call backtrack(1, [3, 3], 1)
no valid combination → return
path.pop() → path = [3]
Loop i = 2 → arr[2] = 6
path.push(6) → path = [3, 6]
Call backtrack(-2, [3, 6], 2)
remainingSum < 0 → return
path.pop() → path = [3]
Loop i = 3 → arr[3] = 7
path.push(7) → path = [3, 7]
Call backtrack(-3, [3, 7], 3)
remainingSum < 0 → return
path.pop() → path = [3]
Loop ends
path.pop() → path = []
Loop i = 2 → arr[2] = 6
path.push(6) → path = [6]
Call backtrack(1, [6], 2)
no valid combination → return
path.pop() → path = []
Loop i = 3 → arr[3] = 7
path.push(7) → path = [7]
Call backtrack(0, [7], 3)
remainingSum == 0 → result.push([7])
path.pop() → path = []
Loop ends
Step 3: End
Return result = [[2, 2, 3], [7]]
Output:
[[2, 2, 3], [7]]
Explanation: The backtracking algorithm explores all possible combinations by adding numbers repeatedly (reuse is allowed). Only the paths where the sum exactly equals target are stored in result.
var combinationSum = function(arr, target) {
let result = [];
let backtrack = (remainingSum, path, start) => {
if(remainingSum === 0) result.push([...path]);
if(remainingSum <= 0) return;
for(let i=start; i < arr.length; i++){
path.push(arr[i]);
backtrack(remainingSum-arr[i], path, i);
path.pop();
}
}
backtrack(target, [], 0);
return result;
};
def combinationSum(arr, target):
result = []
def backtrack(remainingSum, path, start):
if remainingSum == 0:
result.append(list(path))
return
if remainingSum < 0:
return
for i in range(start, len(arr)):
path.append(arr[i])
backtrack(remainingSum - arr[i], path, i)
path.pop()
backtrack(target, [], 0)
return result
# Example
arr = [2, 3, 6, 7]
target = 7
print(combinationSum(arr, target))
import java.util.*;
class Solution {
public List> combinationSum(int[] arr, int target) {
List> result = new ArrayList<>();
List path = new ArrayList<>();
backtrack(arr, target, path, 0, result);
return result;
}
private void backtrack(int[] arr, int remainingSum, List path, int start, List> result) {
if (remainingSum == 0) {
result.add(new ArrayList<>(path));
return;
}
if (remainingSum < 0) return;
for (int i = start; i < arr.length; i++) {
path.add(arr[i]);
backtrack(arr, remainingSum - arr[i], path, i, result);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
Solution s = new Solution();
int[] arr = {2, 3, 6, 7};
int target = 7;
List> ans = s.combinationSum(arr, target);
for (List comb : ans) {
System.out.println(comb);
}
}
}
class Solution {
public:
vector> combinationSum(vector& arr, int target) {
vector> result;
vector path;
function backtrack = [&](int remainingSum, int start) {
if (remainingSum == 0) {
result.push_back(path);
return;
}
if (remainingSum < 0) return;
for (int i = start; i < arr.size(); i++) {
path.push_back(arr[i]);
backtrack(remainingSum - arr[i], i);
path.pop_back();
}
};
backtrack(target, 0);
return result;
}
};
int main() {
Solution s;
vector arr = {2, 3, 6, 7};
int target = 7;
vector> ans = s.combinationSum(arr, target);
for (auto &comb : ans) {
for (int num : comb) cout << num << " ";
cout << endl;
}
}
void backtrack(int arr[], int n, int target, int path[], int pathSize, int start) {
if (target == 0) {
for (int i = 0; i < pathSize; i++) {
printf("%d ", path[i]);
}
printf("\n");
return;
}
if (target < 0) return;
for (int i = start; i < n; i++) {
path[pathSize] = arr[i];
backtrack(arr, n, target - arr[i], path, pathSize + 1, i);
}
}
int main() {
int arr[] = {2, 3, 6, 7};
int n = 4, target = 7;
int path[100];
backtrack(arr, n, target, path, 0, 0);
return 0;
}
using System;
using System.Collections.Generic;
class Solution {
public IList> CombinationSum(int[] arr, int target) {
var result = new List>();
var path = new List();
void Backtrack(int remainingSum, int start) {
if (remainingSum == 0) {
result.Add(new List(path));
return;
}
if (remainingSum < 0) return;
for (int i = start; i < arr.Length; i++) {
path.Add(arr[i]);
Backtrack(remainingSum - arr[i], i);
path.RemoveAt(path.Count - 1);
}
}
Backtrack(target, 0);
return result;
}
}
class Program {
static void Main() {
var s = new Solution();
var arr = new int[] {2, 3, 6, 7};
var ans = s.CombinationSum(arr, 7);
foreach (var comb in ans) {
Console.WriteLine(string.Join(" ", comb));
}
}
}
