Last updated on January 19th, 2025 at 10:57 pm
Here, we see a Combination Sum II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Backtracking
Companies
Snapchat
Level of Question
Medium
Combination Sum II LeetCode Solution
Table of Contents
1. 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.
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] ]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Subsets with Backtracking”. This pattern is commonly used to solve problems where we need to generate all possible combinations or subsets of a given set of elements, often with constraints like avoiding duplicates or meeting a target sum.
3. Code Implementation in Different Languages
3.1 Combination Sum II C++
class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> curr;
int n = candidates.size();
sort(candidates.begin(), candidates.end());
comsum(curr, target, 0, candidates, 0, n);
return result;
}
void comsum(vector<int> &curr, int target, int sum, vector<int> &candidates, int curInd, int n){
if(target == sum){
result.push_back(curr);
return;
}
else if(sum>target){
return;
}
for(int i = curInd; i < n; i++){
if(i != curInd && candidates[i]==candidates[i-1])
continue;
sum += candidates[i];
curr.push_back(candidates[i]);
comsum(curr, target, sum, candidates, i+1, n);
sum -= candidates[i];
curr.pop_back();
}
}
};
3.2 Combination Sum II Java
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> smallAns = new ArrayList<>();
Arrays.sort(candidates);
combinationSum2(candidates, target, 0, smallAns, res);
return res;
}
public int combinationSum2(int[] arr, int tar, int idx, List<Integer> smallAns, List<List<Integer>> res) {
if (tar == 0) {
ArrayList<Integer> base = new ArrayList<>(smallAns);
res.add(base);
return 1;
}
boolean[] visited = new boolean[50];
int count = 0;
for (int i = idx; i < arr.length; ++i) {
if (!visited[arr[i]] && tar - arr[i] >= 0) {
visited[arr[i]] = true;
smallAns.add(arr[i]);
count += combinationSum2(arr, tar - arr[i], i + 1, smallAns, res);
smallAns.remove(smallAns.size() - 1);
}
}
return count;
}
}
3.3 Combination Sum II JavaScript
var combinationSum2 = function(candidates, target) {
if (!candidates) {
return [];
}
if (target === 0) {
return [[]];
}
candidates.sort((a,b) => { return a - b});
let paths = [];
let find = function (t, p, i) {
if (t === 0) {
paths.push(p);
return;
} else {
while (i < candidates.length && t - candidates[i] >= 0) {
find(t - candidates[i], [...p, candidates[i]], i + 1)
i++;
while (candidates[i - 1] === candidates[i]) {
i++;
}
}
}
}
find (target, [], 0);
return paths;
};
3.4 Combination Sum II Python
class Solution(object):
def combinationSum2(self, candidates, target):
candidates.sort()
result = []
self.combine_sum_2(candidates, 0, [], result, target)
return result
def combine_sum_2(self, nums, start, path, result, target):
if not target:
result.append(path)
return
for i in xrange(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
if nums[i] > target:
break
self.combine_sum_2(nums, i + 1, path + [nums[i]],
result, target - nums[i])
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(2n) | O(n) |
| Java | O(2n) | O(n) |
| JavaScript | O(2n) | O(n) |
| Python | O(2n) | O(n) |
- Time Complexity:
- Sorting the input array takes O(n log n).
- The backtracking function explores all possible subsets of the array. In the worst case, there are 2n subsets (where
nis the size of the input array). - For each subset, the function performs operations like adding/removing elements, which are O(1).
- Overall time complexity: O(n log n + 2n) ≈ O(2n) (since 2n dominates n log n for large n).
- Space Complexity:
- The recursion stack can go as deep as the size of the input array (
n), so the space complexity for the recursion stack is O(n). - Additional space is used for storing the result, but this is not considered in the space complexity since it depends on the output size.
- Overall space complexity: O(n).
- The recursion stack can go as deep as the size of the input array (