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]]
首先将数组排一下序，这样如果找到当前的值加起来已经大于目标了就不再找了
还是使用回溯算法，以上面的为例，我们的查找过程是这样的：
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]]
这个问题和上面的区别是，给的元素有可能有重复，但是结果是不能有重复的，且所有元素只能用一次
在同一层递归树中，如果某元素已经处理并进入下一层递归，那么与该元素相同的值就应该跳过。否则将出现重复。
例如：1,1,2,3
如果第一个1已经处理并进入下一层递归1,2,3
那么第二个1就应该跳过，因为后续所有情况都已经被覆盖掉。
而且所有相同元素中应该是第一个进入下一层递归，而不是任意一个
例如：1,1,2,3
如果第一个1已经处理并进入下一层递归1,2,3，那么两个1是可以同时出现在一个解中的
而如果选择的是第二个1并进入下一层递归2,3，那么不会出现两个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) {
//原来我打算在添加的时候遍历整个result数组
//看看有没有一样的
// 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++){
//这里将所有重复元素中的后几个排除掉，不会进入下一层
if(i != start && candidates[i] == candidates[i-1])
continue;
res.push(candidates[i]);
if ((sum+candidates[i])>target){
res.pop();
break;
}
//这里保证一个结果里不会重复用元素
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]]
这个和上面的思想也是一样的，这里多了一个长度和选用元素的限制
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;
}
//这里保证一个结果里不会重复用元素
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?
这里就算顺序不一样也要算上，只需要给出最后方法的数量，估计之前的办法不行了。
试了一下，之前的办法把所有特殊的优化条件都去了，走完完全全的回溯算法，果然超时了。
那也就是说有动态规划的方法，可以利用之前的结果递推。
试想一下，如果现在我们只差一个数字就加到我们的target了，这个数字可能是数组中的任何一个数字，对于每一个这样的数字x，我们找到target-x这个数的组合的个数，于是：
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;
};
这样每个target都找遍所有元素有点浪费，先排个序，然后找到比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;
};
