Combination Sum 1
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7
A solution set is: [[7], [2, 2, 3]]
首先將數(shù)組排一下序，這樣如果找到當(dāng)前的值加起來(lái)已經(jīng)大于目標(biāo)了就不再找了
還是使用回溯算法讹俊，以上面的為例牵啦，我們的查找過(guò)程是這樣的：
2
22
222
2222
223
226
23
233
26
3
33
333
36
6
66
7
var combinationSum = function(candidates, target) {
var result = [];
var num = candidates.length;
candidates.sort(function(a,b){
return a-b;
});
var help = function (res,sum,start) {
if (sum===target) {
result.push(res.concat());
} else if (sum<target) {
for(var i = start; i < num; i++){
res.push(candidates[i]);
if ((sum+candidates[i])>target){
res.pop();
break;
}
help(res,sum+candidates[i],i);
res.pop();
}
}
};
help([],0,0);
return result;
};
Combination Sum 2
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]
這個(gè)問(wèn)題和上面的區(qū)別是迫皱，給的元素有可能有重復(fù)茎活，但是結(jié)果是不能有重復(fù)的昙沦，且所有元素只能用一次
在同一層遞歸樹中，如果某元素已經(jīng)處理并進(jìn)入下一層遞歸载荔，那么與該元素相同的值就應(yīng)該跳過(guò)盾饮。否則將出現(xiàn)重復(fù)。
例如：1,1,2,3
如果第一個(gè)1已經(jīng)處理并進(jìn)入下一層遞歸1,2,3
那么第二個(gè)1就應(yīng)該跳過(guò)懒熙，因?yàn)楹罄m(xù)所有情況都已經(jīng)被覆蓋掉丘损。
而且所有相同元素中應(yīng)該是第一個(gè)進(jìn)入下一層遞歸，而不是任意一個(gè)
例如：1,1,2,3
如果第一個(gè)1已經(jīng)處理并進(jìn)入下一層遞歸1,2,3工扎，那么兩個(gè)1是可以同時(shí)出現(xiàn)在一個(gè)解中的
而如果選擇的是第二個(gè)1并進(jìn)入下一層遞歸2,3徘钥，那么不會(huì)出現(xiàn)兩個(gè)1的解了。
var combinationSum2 = function(candidates, target) {
var result = [];
var used = [];
var num = candidates.length;
candidates.sort(function(a,b){
return a-b;
});
var help = function (res,sum,start) {
if (sum===target) {
//原來(lái)我打算在添加的時(shí)候遍歷整個(gè)result數(shù)組
//看看有沒(méi)有一樣的
// for (var i = result.length - 1;i>=0;i--) {
// if (result[i].length===res.length) {
// for (var j = res.length;j>=0;j--) {
// if (result[i][j]!==res[j])
// break;
// }
// if (j<0)
// return;
// }
// }
result.push(res.concat());
} else if (sum<target) {
for(var i = start; i < num; i++){
//這里將所有重復(fù)元素中的后幾個(gè)排除掉肢娘，不會(huì)進(jìn)入下一層
if(i != start && candidates[i] == candidates[i-1])
continue;
res.push(candidates[i]);
if ((sum+candidates[i])>target){
res.pop();
break;
}
//這里保證一個(gè)結(jié)果里不會(huì)重復(fù)用元素
help(res,sum+candidates[i],i+1);
res.pop();
}
}
};
help([],0,0);
return result;
};
Combination Sum 3
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
example:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
這個(gè)和上面的思想也是一樣的呈础，這里多了一個(gè)長(zhǎng)度和選用元素的限制
var combinationSum3 = function(k, n) {
var result = [];
var used = [];
var candidates = [1,2,3,4,5,6,7,8,9];
var num = candidates.length;
var help = function (res,sum,start) {
if (sum===n&&res.length===k) {
result.push(res.concat());
} else if (sum<n&&res.length<k) {
for(var i = start; i < num; i++){
res.push(candidates[i]);
if ((sum+candidates[i])>n){
res.pop();
break;
}
//這里保證一個(gè)結(jié)果里不會(huì)重復(fù)用元素
help(res,sum+candidates[i],i+1);
res.pop();
}
}
};
help([],0,0);
return result;
};
Combination Sum 4
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
這里就算順序不一樣也要算上，只需要給出最后方法的數(shù)量橱健，估計(jì)之前的辦法不行了而钞。
試了一下，之前的辦法把所有特殊的優(yōu)化條件都去了拘荡，走完完全全的回溯算法臼节，果然超時(shí)了。
那也就是說(shuō)有動(dòng)態(tài)規(guī)劃的方法珊皿，可以利用之前的結(jié)果遞推官疲。
試想一下，如果現(xiàn)在我們只差一個(gè)數(shù)字就加到我們的target了亮隙，這個(gè)數(shù)字可能是數(shù)組中的任何一個(gè)數(shù)字途凫，對(duì)于每一個(gè)這樣的數(shù)字x，我們找到target-x這個(gè)數(shù)的組合的個(gè)數(shù)溢吻，于是：
comb[target] = sum(comb[target - nums[i]]), where 0 <= i < nums.length, and target >= nums[i].
這之中nums[i]就是x
所以：
var combinationSum4 = function(nums, target) {
if (nums.length===0)
return 0;
var dp = [];
dp[0] = 1;
for (var i = 1; i <= target; ++i) {
if (!dp[i])
dp[i] = 0;
for (var j = 0;j <nums.length;j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target] ? dp[target] : 0;
};
這樣每個(gè)target都找遍所有元素有點(diǎn)浪費(fèi)维费，先排個(gè)序，然后找到比target大的就不找了促王，這樣比較快犀盟。
var combinationSum4 = function(nums, target) {
if (nums.length===0)
return 0;
nums.sort(function(a,b){
return a-b;
});
var dp = [];
dp[0] = 1;
for (var i = 1; i <= target; ++i) {
if (!dp[i])
dp[i] = 0;
for (var j = 0;j <nums.length;j++) {
if (i >= nums[j]) {
dp[i] += dp[i - nums[j]];
} else
break;
}
}
return dp[target] ? dp[target] : 0;
};
