
Description
The problem requires finding all unique combinations of numbers from a given list (candidates
) that sum up to a specified target. Each number in the list can be used only once in each combination. The solution set should not contain duplicate combinations, and the combinations can be in any order.
Intuition
To solve the problem, we can use a backtracking approach to explore all possible combinations. Sorting the array helps in easily skipping duplicate elements, which is essential to avoid duplicate combinations in the result set.
Approach
- Sorting: Start by sorting the
candidates
array. This allows us to easily skip over duplicate elements and helps in efficiently pruning the search space. - Backtracking: Implement a recursive backtracking function that: - Adds the current combination to the result list when the target sum is reached. - Recursively explores adding each subsequent number in the sorted list to the current combination. - Skips over any duplicate numbers to ensure each combination is unique. - Stops exploring further when the current sum exceeds the target.
- Pruning: Since the array is sorted, if the current sum exceeds the target at any point, further recursion can be terminated early to save computation.
Complexity
Time Complexity:
O(2^n)
, where n
is the number of elements in the candidates
list. This is due to the backtracking approach, which can potentially explore all subsets.
Space Complexity:
O(n)
, where n
is the number of elements in the candidates
list. This space is used by the recursion stack and the current combination path.
Code
C++
class Solution {
public:
vector> combinationSum2(vector& candidates, int target) {
vector> result;
vector path;
sort(candidates.begin(), candidates.end());
backtracking(result, path, candidates, target, 0, 0);
return result;
}
private:
void backtracking(vector>& result, vector& path, vector& candidates, int target, int start, int sum) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = start; i < candidates.size(); ++i) {
if (i > start && candidates[i] == candidates[i - 1]) continue;
if (sum + candidates[i] > target) break;
path.push_back(candidates[i]);
backtracking(result, path, candidates, target, i + 1, sum + candidates[i]);
path.pop_back();
}
}
};
Python
class Solution:
def combinationSum2(self, candidates, target):
result = []
candidates.sort()
def backtracking(path, start, sum):
if sum == target:
result.append(path[:])
return
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue
if sum + candidates[i] > target:
break
path.append(candidates[i])
backtracking(path, i + 1, sum + candidates[i])
path.pop()
backtracking([], 0, 0)
return result
Java
class Solution {
public List> combinationSum2(int[] candidates, int target) {
List> result = new ArrayList<>();
Arrays.sort(candidates);
backtracking(result, new ArrayList<>(), candidates, target, 0, 0);
return result;
}
private void backtracking(List> result, List path, int[] candidates, int target, int start, int sum) {
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1]) continue;
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(result, path, candidates, target, i + 1, sum + candidates[i]);
path.remove(path.size() - 1);
}
}
}
JavaScript
var combinationSum2 = function (candidates, target) {
let result = []
candidates.sort((a, b) => a - b)
console.log(candidates)
let backtraking = (path, start, sum) => {
if (sum === target) {
result.push(path.slice())
return
}
for (let i = start; i < candidates.length; i++) {
if (i > start && candidates[i] == candidates[i - 1])
continue
if (sum > target)
break
path.push(candidates[i])
backtraking(path, i + 1, sum+candidates[i])
path.pop()
}
}
backtraking([], 0, 0)
return result
};