Dare2Solve
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.
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.
candidates
array. This allows us to easily skip over duplicate elements and helps in efficiently pruning the search space.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.
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.
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(), candidates.end());
backtracking(result, path, candidates, target, 0, 0);
return result;
}
private:
void backtracking(vector<vector<int>>& result, vector<int>& path, vector<int>& 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();
}
}
};
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
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
backtracking(result, new ArrayList<>(), candidates, target, 0, 0);
return result;
}
private void backtracking(List<List<Integer>> result, List<Integer> 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);
}
}
}
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
};