40. Combination Sum II
Combination Sum II
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
- Suppose our array is: [10,1,2,7,6,1,5]. Then after sorting, the array becomes [1,1,2,5,6,7,10]. target = 8.
- When doing depth ownership, the problem becomes:
- [1] + [1,2,5,6,7,10], target=7
- [2] + [1,1,5,6,7,10], target=6
- There is a problem here: how to deduplicate; for example, because there are two 1s, there may be two [1, 7].
- There are two solutions: 1) Determine whether the result already exists each time the result is written. 2) Every time a deep recursion is to be performed, if the element is equal to the previous element, no deep search is performed.
var combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
const dfs = (arr, tmpArr, remain, start) => {
if (remain === 0) result.push(tmpArr.slice());
else if (remain < 0) return;
for (let i = start; i < arr.length; i++) {
if (i !== start && arr[i] === arr[i - 1]) continue;
tmpArr.push(arr[i]);
dfs(arr, tmpArr, remain - arr[i], i + 1);
tmpArr.pop();
}
}
dfs(candidates, [], target, 0);
return result;
};- array sort; // var candidates= [10,1,2,7,6,1,5].; candidates=candidates.sort(function(val1, val2) { return val1>val2?1:val1<val2?-1:0; }); candidates= [1,1,2,5,6,7,10];
- Each number in C may only be used once in the combination.
- Since Step 2, The maximum length of the returned array is candidates.length;
- Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
var combinationSum2 = function(candidates, target) {
candidates = candidates.sort(function(val1, val2) { // step 1
return val1>val2?1:val1<val2?-1:0;
});
var solution = [], result = [], used = []; // used = []; step 2
var pushVal = function(solution, n) {
for(var sum=0,i=0; i<solution.length; ++i){
sum += solution[i];
}
return sum<target?false:(sum==target&&solution.length==n)?result.push(solution.slice(0)):true;
}
var backTracking = function(k, n) { // step 5
if(k!=n){
var last_num = ""; // candidates= [1,1,2,5,6,7,10]; target=8; A:[candidates[0]=1,candidates[1]=1,candidates[4]=6], B:[candidates[1]=1,candidates[0]=1,candidates[4]=6], A=B. A,B only one, need.
for(var i=0; i<candidates.length; ++i){
if(k>0 && solution[k-1]>candidates[i]) { continue; } // step 4
if(used[i]) { continue; }
if(last_num ==candidates[i]) { continue; }
used[i] = true;
last_num = candidates[i];
solution[k] = candidates[i];
if(pushVal(solution, n)){ used[i]=false; solution.splice(solution.length-1); return true; }
arguments.callee(k+1, n);
used[i] = false;
solution.splice(solution.length-1);
}
}else{ return false; }
}
for(var i=1; i<=candidates.length; ++i){ // step 3
backTracking(0, i);
}
return result;
};Approach) Recursion
Dealing with these kinds of questions would generally be better to sort the array first.
var combinationSum2 = function(candidates, target) {
var result = []
candidates.sort((a,b) => a-b)
var helper = function(candidates, target, tmpArr, idx){
if(target == 0){ // when target reaches zero, means that you can push it into the result
result.push(tmpArr.slice())
return
}
if(target < 0){ //with recursion, your 'target' might get reduced till below zero and at that point of time it's time to stop the recursion
return
}
for(var i = idx; i < candidates.length; i++){ //simulating whether to take or not to take every single digit
if(idx == i || candidates[i] != candidates[i - 1]){
tmpArr.push(candidates[i])
helper(candidates, target - candidates[i], tmpArr, i + 1)
tmpArr.pop()
}
}
}Approach) KnapSack Pattern
This question is a little different from the rest Combination Sum problems apart from having a bounded knapsack which means we cannot re-use the same element twice; we have to handle duplicates too.
One way to handle duplicates is to create a set/hashmap and push string of sorted temp arrays but it gives TLE since we sort the temp arrays in every recursive call and then convert it to string. These operations are O(NLogN) and O(N) respectively, which won't matter much practically as we are given a small input size but definitely has more time complexity, which can be reduced.
Our Recursive function itself has O(2^N) time complexity, so it's better to add more time complexity parallel to it instead of inside it.
A better way to do this is to pre-sort the array before applying recursion and then we will have all same elements alongside, then after using one of the same elements, we can simply use a while loop to move the pointer and skip the remaining same elements (First One)
var combinationSum2 = function(candidates, target) {
// edge cases
if(!candidates || candidates.length == 0 || ! target || target < 0){return []}
else if(candidates.length === 1){
if(candidates[0] === target){return [[target]]}
else{return []}
}
let result = [] // will hold final result
candidates.sort((a,b) => a-b) // sort in non decre order
combinationSum2Recursive(candidates, target, candidates.length, [], result)
return result
};
var combinationSum2Recursive = function(A, target, n, temp, result){
// base case 1
if(target === 0){
result.push([...temp])
return
}
// base case 2
if(n === 0){return}
// when element is not valid
if(A[n-1] > target){
/* (this will fix the TLE error)
this while loop logic is used to avoid duplicates in our ans; we simply iterate the pointer and skip same elements
because for example in [1,2,2,2] if we have pointer at last element and we plan to NOT CHOOSE IT,
then it makes sense that we don't chose the remaining 2's too, so we keep on moving our pointer until we skip every one of them
*/
while(A[n-1] === A[n-2]){
n-=1
}
return combinationSum2Recursive(A, target, n-1, temp, result) // element NOT chosen
}
// element is valid - we have two cases
// Case 1: when we choose it
temp.push(A[n-1]) // push to temp arr
combinationSum2Recursive(A, target-A[n-1], n-1, temp, result) // element chosen
temp.pop() // dont forget to remove from temp after processing
// Case 2: when we don't choose it
/* (this will fix the TLE error)
this while loop logic is used to avoid duplicates in our ans; we simply iterate the pointer and skip same elements
because for example in [1,2,2,2] if we have pointer at last element and we plan to NOT CHOOSE IT,
then it makes sense that we don't chose the remaining 2's too, so we keep on moving our pointer until we skip every one of them
*/
while(A[n-1] === A[n-2]){
n-=1
}
combinationSum2Recursive(A, target, n-1, temp, result) // element NOT chosen
}var recur = function(nums, target, start, temp, result){
// base case
if(target < 0)
return
if(target === 0){
const t = [...temp]
result.push(t)
return
}
let i = start
while(i < nums.length){
temp.push(nums[i])
recur(nums, target-nums[i], i+1, temp, result)
temp.pop()
// smart way : skip the same elements after using one of them
while(i < nums.length-1 && nums[i+1] === nums[i])
i+=1
i+=1
}
}
var combinationSum2 = function(nums, target) {
// sanity checks
if(!nums || nums.length === 0)
return []
if(nums.length === 1){
if(target < nums[0]) return []
else if(target === nums[0]) return [nums]
}
nums.sort((a,b) => a-b) // pre sort
const result = []
recur(nums, target, 0, [], result)
return result
};
Conclusion
That’s all folks! In this post, we solved LeetCode problem #40. Combination Sum II
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment