39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) 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]
]
S： backtracking
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> sum;
getSum(candidates, sum, result, 0, target);
return result;
}
void getSum(vector<int>& candidate, vector<int> sum, vector<vector<int>>& result, int idx, int target){
if(target == 0){
result.push_back(sum);
return;
}
if(idx == candidate.size()) return;
while(target >= 0){
getSum(candidate, sum, result, idx+1, target);
sum.push_back(candidate[idx]);
target = target - candidate[idx];
}
}
40. Combination Sum II
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]
]
S: backtracking
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> sum;
vector<vector<int>> result;
getSum(candidates, sum, result, 0, target);
return result;
}
void getSum(vector<int>& candidates, vector<int> sum, vector<vector<int>>& result, int idx, int target) {
if(target == 0) {
result.push_back(sum);
return;
}
if(idx == candidates.size() || candidates[idx] > target) return;
int count = 1;
idx++;
while(idx < candidates.size() && candidates[idx] == candidates[idx-1]) {
count++;
idx++;
}
while(count >= 0 && target >= 0) {
getSum(candidates, sum, result, idx, target);
sum.push_back(candidates[idx-1]);
target -= candidates[idx-1];
count--;
}
}
216. Combination Sum III
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 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
S:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> sum;
getSum(k, 1, n, result, sum);
return result;
}
void getSum(int k, int num, int n, vector<vector<int>>& result, vector<int> sum) {
if(n == 0 && k == 0){
result.push_back(sum);
return;
}
if(num > 9 || n <= 0) return;
getSum(k, num+1, n, result, sum);
sum.push_back(num);
getSum(k-1, num+1, n-num, result, sum);
}
254. Factor Combinations
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
S:backtracking
这里有个trick是每次循环i都从上次找到的factor开始，因为小于上个factor的已经算过，这样可以避免重复元素也可以减少循环次数。
用i <= sqrt(n) 作为循环终止条件，保证结果升序排列以避免重复
vector<vector<int>> getFactors(int n) {
vector<int> sum;
vector<vector<int>> result;
getComb(result, sum, n, 2);
return result;
}
void getComb(vector<vector<int>>& result, vector<int> sum, int n, int factor) {
for(int i = factor; i <= sqrt(n); ++i) {
if(n%i == 0){
vector<int> new_sum = sum;
new_sum.push_back(i);
getComb(result, new_sum, n/i, i);
new_sum.push_back(n/i);
result.push_back(new_sum);
}
}
}
377. Combination Sum IV
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?
S1: recursion O(n!) factorial
题意分析：需注意从例子看(1, 1, 2) != (2, 1, 1)，所以要考虑每种分法的所有permutation。
递归结构：穷举加法中的第一个数v，递归调用计算构成target-v的所有可能性(要求v<=target)
结束条件：target = 0，返回1
边界条件：target <= 0，直接返回0，注意这和递归结束条件不同
int combinationSum4(vector<int>& nums, int target) {
if (target<=0) return 0;
return combinationSumRecur(nums, target);
}
int combinationSumRecur(vector<int>& nums, int target) {
if (target == 0) return 1;
int count = 0;
for (int v : nums)
if (v <= target) count += combinationSumRecur(nums, target-v);
return count;
}
S2: DP O(tn) t为target大小
存储recursion的中间结果， count[i]表示target=i时的结果，count[0]初始为1因为当num = i时count[i - num]应为1.
int combinationSum4(vector<int>& nums, int target) {
if(target <= 0) return 0;
int n = nums.size();
vector<int> count(target+1, 0);
count[0] = 1;
for(int i = 1; i <= target; ++i){
for(int num: nums){
if(i - num >= 0) count[i] += count[i-num];
}
}
return count[target];
}