39. Combination Sum
Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1 Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40- All elements of
candidatesare distinct. 1 <= target <= 40
var combinationSum = function(candidates, target) {
var arr = [];
var result = [];
recursion(candidates, target, "", arr,result);
return result;
};
var recursion = function(candidates, target, acc, arr, result) {
if(target == 0) {
var str = acc.substring(1,acc.length);
var temp = str.split(",")
temp = temp.sort((a,b)=>{return a-b});
str = temp.join(",");
if(!arr.includes(str)) {
arr.push(str);
var arr = [];
for(let i=0; i < temp.length; i++) {
arr.push(Number(temp[i]));
}
result.push(arr);
}
return ;
}
for(let i=0; i < candidates.length; i++) {
if(target>0) {
recursion(candidates, target - candidates[i], acc+","+candidates[i],arr,result);
}
}
}Approach) Depth First Search (DFS)
function combinationSum(candidates, target) {
let res = [];
const dfs = (curCandidates, curTarget, value) => {
if( curTarget == 0) res.push(value);
if(curTarget <= 0 ) return;
for(let g=0; g<curCandidates.length; g++){
dfs(curCandidates.slice(g), curTarget-curCandidates[g], [...value, curCandidates[g] ] );
}
}
dfs(candidates, target, []);
return res;
}Approach) Depth First Search (DFS) + Sort
var combinationSum = function (candidates, target) {
if (!candidates || candidates.length == 0) return [];
let res = [];
candidates.sort((a, b) => a - b); //prepare prefix sum
var helper = function (curSum, cur, index) {
if (curSum == target) {
res.push([...cur]);
return;
}
for (let i = index; i < candidates.length; i++) {
if (curSum > target) return; //prune no valid then pop
cur.push(candidates[i]);
helper(curSum + candidates[i], cur, i); //can se duplicate ele
console.log("index: ", index)
console.log("i: ", i)
cur.pop();
}
}
helper(0, [], 0);
return res;
};One could think of this as a variant of the knapsack problem, with the added requirement of recording all possible combinations that achieve the target. Here we use a recursive approach, continually pushing on different candidate values until either we go over our target, or we find a valid combination.
var combinationSum = function(candidates, target) {
let list = []
helper(list, [], candidates, target, 0)
return list
};
let helper = function(list, tempList, candidates, target, start) {
if (target < 0) return
else if (target == 0) list.push(tempList.slice())
else {
for (let i = start; i < candidates.length; i++) {
tempList.push(candidates[i])
helper(list, tempList, candidates, target - candidates[i], i)
tempList.pop()
}
}
}
var combinationSum = function(candidates, target) {
if(!candidates.length) {
return [];
}
let arr1 = [];
if(target>candidates[0]) {
arr1 = combinationSum(candidates, target-candidates[0]);
if(arr1.length) {
arr1.forEach(v=>v.unshift(candidates[0]));
}
}else if(target==candidates[0]) {
arr1 = [[candidates[0]]];
}
let arr2 = combinationSum(candidates.slice(1), target);
return arr1.concat(arr2);
};Approach) Short Recursion
Idea
Walk through each number in the candidates by index.
Base case
if t is 0, meaning the sum is equal to target, return
if t is less than 0, return
Recursion
Use all the possible num of candidates starting from idx to end. idx is needed to ensure we don't have duplicate result. For example, without idx we would get [2, 2, 3] and [3, 2, 2].
Note
Sorting is optionally here since the problem states they're all distinct numbers
var combinationSum = function(candidates, target) {
const result = [];
const helper = (t, arr, idx) => {
if(t === 0) return result.push(arr);
else if (t < 0) return;
for(let i = idx; i < candidates.length; i++) {
const num = candidates[i];
helper(t - num, [...arr, num], i);
}
};
helper(target, [], 0);
return result;
};const combinationSum = function(c, t) {
let dp = buildDPTable(t);
c.forEach(candidate => {
for (let num = 1; num <= t; num++) {
if (candidate <= num) {
let prevComb = num - candidate;
dp[prevComb].forEach(comb => {
let dup = [...comb];
dup.push(candidate);
dp[num].push(dup);
});
};
};
});
return dp[dp.length-1];
};
const buildDPTable = function(size) {
let dp = new Array(size+1);
for (let i = 0; i < dp.length; i++) {
dp[i] = [];
};
dp[0] = [[]];
return dp;
}Conclusion
That’s all folks! In this post, we solved LeetCode problem #39. Combination Sum
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