Problem Statement:
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
Approach:
- Sort the array → ensures duplicates are adjacent and helps in skipping them.
- Use backtracking to explore all possible combinations:
- Keep reducing the
remainingSum. - If it
becomes 0, add the current path to result. - If it
becomes negative, stop exploring further.
- Keep reducing the
- Skip duplicates → when iterating, if the current number is the same as the previous
(arr[i] === arr[i-1])and not at the starting index of the loop, continue to next iteration. - Move forward (use
i+1) because each element can only be used once.
Time Complexity:
Time Complexity = O(2n * n)
Space Complexity:
Space Complexity = O(2n * n) (output) + O(n) (stack)
Dry Run
Input: arr = [2, 3, 6, 7], target = 7
Step 0: Start Function combinationSum2([2, 3, 6, 7], 7)
Sort arr → arr = [2, 3, 6, 7]
Initialize:
result = []
path = []
Call backtrack(7, [], 0)
Loop i = 0 → arr[0] = 2
path.push(2) → path = [2]
Call backtrack(5, [2], 1)
Loop i = 1 → arr[1] = 3
path.push(3) → path = [2, 3]
Call backtrack(2, [2, 3], 2)
Loop i = 2 → arr[2] = 6 → exceeds remainingSum → stop
Loop i = 3 → arr[3] = 7 → exceeds remainingSum → stop
path.pop() → path = [2]
Loop i = 2 → arr[2] = 6
path.push(6) → path = [2, 6]
Call backtrack(-1, [2, 6], 3)
remainingSum < 0 → return
path.pop() → path = [2]
Loop i = 3 → arr[3] = 7
path.push(7) → path = [2, 7]
Call backtrack(-2, [2, 7], 4)
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], 2)
Loop i = 2 → arr[2] = 6
path.push(6) → path = [3, 6]
Call backtrack(-2, [3, 6], 3)
remainingSum < 0 → return
path.pop() → path = [3]
Loop i = 3 → arr[3] = 7
path.push(7) → path = [3, 7]
Call backtrack(-3, [3, 7], 4)
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], 3)
Loop i = 3 → arr[3] = 7 → exceeds remainingSum → stop
path.pop() → path = []
Loop i = 3 → arr[3] = 7
path.push(7) → path = [7]
Call backtrack(0, [7], 4)
remainingSum == 0 → result.push([7])
path.pop() → path = []
Loop ends
Step 3: End
Return result = [[7]]
Output:
[[7]]
Explanation: Unlike combinationSum, here each element can be used at most once (recursion advances with i+1). That’s why [2, 2, 3] is not included, leaving only [7] as the valid combination.
var combinationSum2 = function(arr, target) {
let result = [];
arr.sort((a,b) => (a-b));
let backtrack = (remainingSum, path, start) => {
if(remainingSum == 0){
result.push([...path]);
}
if(remainingSum <= 0) return;
for(let i=start; i start && arr[i-1] === arr[i])
continue;
path.push(arr[i]);
backtrack(remainingSum - arr[i], path, i+1);
path.pop();
}
}
backtrack(target, [], 0);
return result;
};
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
result = []
def backtrack(remaining, path, start):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(remaining - candidates[i], path, i+1)
path.pop()
backtrack(target, [], 0)
return result
import java.util.*;
class Solution {
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] arr, int remaining, int start, List path, List> result) {
if (remaining == 0) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < arr.length && arr[i] <= remaining; i++) {
if (i > start && arr[i] == arr[i-1]) continue;
path.add(arr[i]);
backtrack(arr, remaining - arr[i], i+1, path, result);
path.remove(path.size() - 1);
}
}
}
class Solution {
public:
vector> combinationSum2(vector& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector> result;
vector path;
backtrack(candidates, target, 0, path, result);
return result;
}
private:
void backtrack(vector& arr, int remaining, int start, vector& path, vector>& result) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int i = start; i < arr.size() && arr[i] <= remaining; i++) {
if (i > start && arr[i] == arr[i-1]) continue;
path.push_back(arr[i]);
backtrack(arr, remaining - arr[i], i + 1, path, result);
path.pop_back();
}
}
};
int cmp(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
void backtrack(int* arr, int arrSize, int remaining, int start,
int* path, int pathSize, int** results, int* colSizes, int* returnSize) {
if (remaining == 0) {
results[*returnSize] = (int*)malloc(pathSize * sizeof(int));
for (int i = 0; i < pathSize; i++) results[*returnSize][i] = path[i];
colSizes[*returnSize] = pathSize;
(*returnSize)++;
return;
}
for (int i = start; i < arrSize && arr[i] <= remaining; i++) {
if (i > start && arr[i] == arr[i-1]) continue;
path[pathSize] = arr[i];
backtrack(arr, arrSize, remaining - arr[i], i+1, path, pathSize+1, results, colSizes, returnSize);
}
}
using System;
using System.Collections.Generic;
public class Solution {
public IList> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
IList> result = new List>();
Backtrack(candidates, target, 0, new List(), result);
return result;
}
private void Backtrack(int[] arr, int remaining, int start, List path, IList> result) {
if (remaining == 0) {
result.Add(new List(path));
return;
}
for (int i = start; i < arr.Length && arr[i] <= remaining; i++) {
if (i > start && arr[i] == arr[i-1]) continue;
path.Add(arr[i]);
Backtrack(arr, remaining - arr[i], i+1, path, result);
path.RemoveAt(path.Count - 1);
}
}
}
