# 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]
]


## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
if(remain<0)      return;
if(remain==0){
res.push_back(temp);
return;
}
for(int i=start;i<candidates.size();++i){
temp.push_back(candidates[i]);
backtracking(res,temp,candidates,remain-candidates[i],i);//notice here
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
vector<int> temp;
vector<vector<int>> res;
backtracking(res,temp,candidates,target,0);
return res;
}
};


# 22. Generate Parentheses

## Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]


## code

class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
if(remain<0)      return;
if(remain==0){
res.push_back(temp);
return;
}
for(int i=start;i<candidates.size();++i){
temp.push_back(candidates[i]);
backtracking(res,temp,candidates,remain-candidates[i],i);
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
vector<int> temp;
vector<vector<int>> res;
backtracking(res,temp,candidates,target,0);
return res;
}
};


# 90. Subsets II

## Description

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]


## code

class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & nums,int start){
res.push_back(temp);
for(int i=start;i<nums.size();++i){
if(i>start && nums[i]==nums[i-1])  continue;//discard the duplicates
temp.push_back(nums[i]);
backtracking(res,temp,nums,i+1);
temp.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
sort(nums.begin(),nums.end());
backtracking(res,temp,nums,0);
return res;
}
};


# hello 2017！

2016-12-31 更新: 大作业已经写完了，感谢两位女神帮忙写文档。想起来其中一位还是我的公众号五位首批关注者之一，深感欣慰。

“无他，唯手熟尔。”

# 43. Multiply Strings

## Description

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

1.The numbers can be arbitrarily large and are non-negative.

2.Converting the input string to integer is NOT allowed.

3.You should NOT use internal library such as BigInteger.

## Analysis

123*45为例:

## code

class Solution {
public:
string multiply(string num1, string num2) {
const int res_size=num1.size()+num2.size();
int res[res_size]={0};
int i=0,j=0,sum=0;
string result;
for(i=num1.size()-1;i>=0;i--){
for(j=num2.size()-1;j>=0;j--){
int p1=i+j;
int p2=i+j+1;
sum=(num1[i]-'0')*(num2[j]-'0')+res[p2];
res[p1]+=sum/10;
res[p2]=sum%10;
}
}
while(res[i]==0 )   i++;
for(i;i<res_size;i++){
result.push_back('0'+res[i]);
if(result.empty())
return "0";
else
return result;
}
};


a = (aN-1aN-2…a1a0)10 = aN-1x10N-1 + aN-2x10N-2 + … + a1x101 + a0x100

b = (bN-1bN-2…b1b0)10 = bN-1x10N-1 + bN-2x10N-2 + … + b1x101 + b0x100

c = a x b = c2N-2x102N-2 + c2N-3x102N-3 + … + c1x101 + c0x100

ck = a0xbk + a1xbk-1 + … + ak-2xb2 + ak-1xb1 + akxb0 + ak+1xb-1 + … + aN-2xb-(N-2-k) + aN-1xb-(N-1-k)

a = (678)10 = 6x102 + 7x101 + 8x100

b = (432)10 = 4x102 + 3x101 + 2x100

c = a x b = 104xc4 + 103xc3 + 102xc2 + 101xc1 + 100xc0 = 10000x24 + 1000x46 + 100x65 + 10x38 + 1x16 = 292896

{ a7, a6, a5, a4, a3, a2, a1, a0 } = { 0, 0, 0, 0, 0, 6, 7, 8 }

{ b7, b6, b5, b4, b3, b2, b1, b0 } = { 0, 0, 0, 0, 0, 4, 3, 2 }

ω = e-2πi/N = e-2πi/8 = e-πi/4 = cos(-π/4) + i sin(-π/4) = √2 / 2 - i √2 / 2 ≈ 0.7-0.7i

ω8 = ω0 = e0 = 1

ω9 = ω1 = e-πi/4 = cos(-π/4) + i sin(-π/4) ≈ 0.7-0.7i

ω10 = ω2 = e-πi/2 = cos(-π/2) + i sin(-π/2) = -i

ω11 = ω3 = e-3πi/4 = cos(-3π/4) + i sin(-3π/4) ≈ -0.7-0.7i

ω12 = ω4 = e-πi = cos(-π) + i sin(-π) = -1

ω13 = ω5 = e-5πi/4 = cos(-5π/4) + i sin(-5π/4) ≈ -0.7+0.7i

ω14 = ω6 = e-3πi/2 = cos(-3π/2) + i sin(-3π/2) = i

ω15 = ω7 = e-7πi/4 = cos(-7π/4) + i sin(-7π/4) ≈ 0.7+0.7i

A4 = a0xω0x4 + a1xω1x4 + a2xω2x4 = 8xω0 + 7xω4 + 6xω8 = 8x1 + 7x(-1) + 6x1 = 7 A5 = a0xω0x5 + a1xω1x5 + a2xω2x5 = 8xω0 + 7xω5 + 6xω10 ≈ 8x1 + 7x(-0.7 + 0.7i) + 6x(-i) = 3.1-1.1i

A6 = a0xω0x6 + a1xω1x6 + a2xω2x6 = 8xω0 + 7xω6 + 6xω12 = 8x1 + 7xi + 6x(-1) = 2+7i A7 = a0xω0x7 + a1xω1x7 + a2xω2x7 = 8xω0 + 7xω7 + 6xω14 ≈ 8x1 + 7x(0.7 + 0.7i) + 6xi = 12.9+10.9i 同样，当 n > 2 时，bn = 0，于是： B0 = b0xω0x0 + b1xω1x0 + b2xω2x0 = 2xω0 + 3xω0 + 4xω0 = 2x1 + 3x1 + 4x1 = 9 B1 = b0xω0x1 + b1xω1x1 + b2xω2x1 = 2xω0 + 3xω1 + 4xω2 ≈ 2x1 + 3x(0.7 - 0.7i) + 4x(-i) = 4.1-6.1i B2 = b0xω0x2 + b1xω1x2 + b2xω2x2 = 2xω0 + 3xω2 + 4xω4 = 2x1 + 3x(-i) + 4x(-1) = -2-3i B3 = b0xω0x3 + b1xω1x3 + b2xω2x3 = 2xω0 + 3xω3 + 4xω6 ≈ 2x1 + 3x(-0.7 - 0.7i) + 4xi = -0.1+1.9i

B4 = b0xω0x4 + b1xω1x4 + b2xω2x4 = 2xω0 + 3xω4 + 4xω8 = 2x1 + 3x(-1) + 4x1 = 3 B5 = b0xω0x5 + b1xω1x5 + b2xω2x5 = 2xω0 + 3xω5 + 4xω10 ≈ 2x1 + 3x(-0.7 + 0.7i) + 4x(-i) = -0.1-1.9i

B6 = b0xω0x6 + b1xω1x6 + b2xω2x6 = 2xω0 + 3xω6 + 4xω12 = 2x1 + 3xi + 4x(-1) = -2+3i B7 = b0xω0x7 + b1xω1x7 + b2xω2x7 = 2xω0 + 3xω7 + 4xω14 ≈ 2x1 + 3x(0.7 + 0.7i) + 4xi = 4.1+6.1i

{ A7, A6, A5, A4, A3, A2, A1, A0 } = { 12.9+10.9i, 2+7i, 3.1-1.1i, 7, 3.1+1.1i, 2-7i, 12.9-10.9i, 21 }

{ B7, B6, B5, B4, B3, B2, B1, B0 } = { 4.1+6.1i, -2+3i, -0.1-1.9i, 3, -0.1+1.9i, -2-3i, 4.1-6.1i, 9 }

= { -13.6+123.4i, -25-8i, -2.4-5.8i, 21, -2.4+5.8i, -25+8i, -13.6-123.4i, 189 }

ω = e2πi/N = e2πi/8 = eπi/4 = cos(π/4) + i sin(π/4) = √2 / 2 + i √2 / 2 ≈ 0.7+0.7i

ω0 = e0 = 1

ω1 = eπi/4 = cos(π/4) + i sin(π/4) ≈ 0.7+0.7i

ω2 = eπi/2 = cos(π/2) + i sin(π/2) = i

ω3 = e3πi/4 = cos(3π/4) + i sin(3π/4) ≈ -0.7+0.7i

ω4 = eπi = cos(π) + i sin(π) = -1

ω5 = e5πi/4 = cos(5π/4) + i sin(5π/4) ≈ -0.7-0.7i

ω6 = e3πi/2 = cos(3π/2) + i sin(3π/2) = -i

ω7 = e7πi/4 = cos(7π/4) + i sin(7π/4) ≈ 0.7-0.7i

c2 = (1/N) x ( C0xω0x2 + C1xω1x2 + C2xω2x2 + C3xω3x2 + C4xω4x2 + C5xω5x2 + C6xω6x2 + C7xω7x2 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω2 + (-25+8i)xω4 + (-2.4+5.8i)xω6 + 21xω8 + (-2.4-5.8i)xω10 + (-25-8i)xω12 + (-13.6+123.4i)xω14 ) = 0.125 x ( 189x1 + (-13.6-123.4i)x(i) + (-25+8i)x(-1) + (-2.4+5.8i)x(-i) + 21x1 + (-2.4-5.8i)x(i) + (-25-8i)x(-1) + (-13.6+123.4i)x(-i) ) ≈ 0.125 x 518.4 = 64.8 ≈ 65 c3 = (1/N) x ( C0xω0x3 + C1xω1x3 + C2xω2x3 + C3xω3x3 + C4xω4x3 + C5xω5x3 + C6xω6x3 + C7xω7x3 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω3 + (-25+8i)xω6 + (-2.4+5.8i)xω9 + 21xω12 + (-2.4-5.8i)xω15 + (-25-8i)xω18 + (-13.6+123.4i)xω21 ) ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(-0.7+0.7i) + (-25+8i)x(-i) + (-2.4+5.8i)x(0.7+0.7i) + 21x(-1) + (-2.4-5.8i)x(0.7-0.7i) + (-25-8i)x(i) + (-13.6+123.4i)x(-0.7-0.7i) ) = 0.125 x 364.32 = 45.54 ≈ 46

c4 = (1/N) x ( C0xω0x4 + C1xω1x4 + C2xω2x4 + C3xω3x4 + C4xω4x4 + C5xω5x4 + C6xω6x4 + C7xω7x4 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω4 + (-25+8i)xω8 + (-2.4+5.8i)xω12 + 21xω16 + (-2.4-5.8i)xω20 + (-25-8i)xω24 + (-13.6+123.4i)xω28 ) = 0.125 x ( 189x1 + (-13.6-123.4i)x(-1) + (-25+8i)x1 + (-2.4+5.8i)x(-1) + 21x1 + (-2.4-5.8i)x(-1) + (-25-8i)x1 + (-13.6+123.4i)x(-1) ) = 0.125 x 192 = 24

c5 = (1/N) x ( C0xω0x5 + C1xω1x5 + C2xω2x5 + C3xω3x5 + C4xω4x5 + C5xω5x5 + C6xω6x5 + C7xω7x5 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω5 + (-25+8i)xω10 + (-2.4+5.8i)xω15 + 21xω20 + (-2.4-5.8i)xω25 + (-25-8i)xω30 + (-13.6+123.4i)xω35 ) ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(-0.7-0.7i) + (-25+8i)x(i) + (-2.4+5.8i)x(0.7-0.7i) + 21x(-1) + (-2.4-5.8i)x(0.7+0.7i) + (-25-8i)x(-i) + (-13.6+123.4i)x(-0.7+0.7i) ) = 0.125 x 3.04 = 0.38 ≈ 0 c6 = (1/N) x ( C0xω0x6 + C1xω1x6 + C2xω2x6 + C3xω3x6 + C4xω4x6 + C5xω5x6 + C6xω6x6 + C7xω7x6 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω6 + (-25+8i)xω12 + (-2.4+5.8i)xω18 + 21xω24 + (-2.4-5.8i)xω30 + (-25-8i)xω36 + (-13.6+123.4i)xω42 ) = 0.125 x ( 189x1 + (-13.6-123.4i)x(-i) + (-25+8i)x(-1) + (-2.4+5.8i)x(i) + 21x1 + (-2.4-5.8i)x(-i) + (-25-8i)x(-1) + (-13.6+123.4i)x(i) ) = 0.125 x 1.6 = 0.2 ≈ 0 c7 = (1/N) x ( C0xω0x7 + C1xω1x7 + C2xω2x7 + C3xω3x7 + C4xω4x7 + C5xω5x7 + C6xω6x7 + C7xω7x7 ) = (1/8) x ( 189xω0 + (-13.6-123.4i)xω7 + (-25+8i)xω14 + (-2.4+5.8i)xω21 + 21xω28 + (-2.4-5.8i)xω35 + (-25-8i)xω42 + (-13.6+123.4i)xω49 ) ≈ 0.125 x ( 189x1 + (-13.6-123.4i)x(0.7-0.7i) + (-25+8i)x(-i) + (-2.4+5.8i)x(-0.7-0.7i) + 21x(-1) + (-2.4-5.8i)x(-0.7+0.7i) + (-25-8i)x(i) + (-13.6+123.4i)x(0.7+0.7i) ) = 0.125 x 3.68 = 0.46 ≈ 0 这样，我们就使用离散傅里叶变换和逆变换计算出了向量 {ai} 和向量 {bj} 的卷积向量 {ck}，如下所示： { c7, c6, c5, c4, c3, c2, c1, c0 } = { 0, 0, 0, 0, 24, 46, 65, 38, 16 } 这和我们在前面直接使用向量 {ai} 和向量 {bj} 来计算卷积的结果是一样的。

2 x log2B + log2N + 几个 x log2log2N < 53