Combination Sum Or Coin change
322. Coin Change
Bottom-up look backward
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int n = coins.size();
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
// look backward
if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
dp[i] = min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};Bottom-up look forward
Be careful, we may have an overflow error in the following test case
[1,2147483647]
2We have to use the long long data type to get rid of the overflow. From this point of view, look backward is a better choice.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int n = coins.size();
vector<long long> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (long long i = 0; i <= amount; ++i) {
for (auto coin : coins) {
// look forward
if (dp[i] != INT_MAX && i + coin <= amount) {
dp[i + coin] = min( dp[i + coin], dp[i] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : int(dp[amount]);
}
};377. Combination Sum IV
https://leetcode.com/problems/combination-sum-iv/
The following code, if we don’t use unsigned int or unsigned long long, we will get overflow at the test case of
[3,33,333] 10000
It is interesting to see that dp[396] will have a super large number.
1941940377
Why we get this number?
396 = 3*132
one way by using 132 3s
396 = 33*12
We have bunch of ways to combine 33 and 3. Such as
1, 33
2,33
3,33
…
we will have approximate 2^(132–10) in total
it will makes the result very large.
396=333+63
This explains why we will get overflow.
Solve approach: using large size int such as unsigned int, or unsigned long long
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned long long> dp(target+1, 0);
dp[0] = 1;
for (unsigned long long sum=0;sum<=target;++sum){
for(auto &num:nums){
unsigned long long new_sum = sum+(unsigned long long)num;
if (new_sum <= target){
dp[new_sum]+=dp[sum];
}
}
}
return int(dp[target]);
}
};518. Coin Change 2
https://leetcode.com/problems/coin-change-2/
class Solution {
public:
int change(int amount, vector<int>& coins) {
const int k= coins.size();
vector<int> dp(amount+1);
dp[0] = 1;
for(auto &c:coins){
for(int pos=0;pos<=amount;++pos){
if(pos-c>=0)dp[pos]+=dp[pos-c];
}
}
return dp[amount];
}
};The difference of these two examples
The difference between the above two questions are:
the first one, repeating is allowed, while the second one is not. The first one is like a permutation and the second one is a combination. I will summary by one example.
coins [1,2]
sum=4.
problem 1:
we will have
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2
for problem 2 we will have
1 1 1 1
1 1 2
2 2
For the first problem, the transitions are easy to build.
For the second one, we have to add some constraints to make sure there is no over counting.
We can build the constrains by using the first K coins only and used coins should be in sorted order.
In order to solve the problem, we can define the state more detail, saying that:
using first K coins only to achieve a specified sum.
For the same example.
If we only use first coin, we can have:
dp(k=1, sum=1) is {1}, we pick only one coin with value of 1
Here k=1 means we only use first 1 coins.
dp(k=1, sum=2) is {1, 1},we pick only two coins with value of 1
dp(k=1, sum=3) is {1,1,1}
dp(k=1, sum=4) is {1,1,1,1}
If we only use first two coins, we can have:
dp(k=2, sum=1) will contains:
case 1) only uses first k-1 coins, which is only using the first coin. It is dp(k=1, sum=1)
case 2) use first k-1 coins and use the k coin. In order to achieve to sum=1 position, we need dp(k=2, sum=1–2), as sum is a negative number, this case is infeasible.
dp(k=2, sum=2) will contains:
case 1) only use first k-1 coins, which is only using the first coin. It is dp(k=1, sum=2), this is the case of {1,1}
case 2) use first k-1 coins and use the k coin. In order to achieve to sum=1 position, we need dp(k=2, sum=2–2), this time sum=0, we have the base case dp(k=2, sum=0) as 1. It is actaully the case of {coin with value of 2}
dp(k=2, sum=3)
case 1) {1,1,1}
case 2) {1,2}
dp(k=2, sum=4)
case 1) {1,1,1,1}
case 2) {1,1,2}, {2,2}
At this time, the transitions of problem 2 should be clear. We can define two dimensional DP as DP[k][sum] it means by using the first k coins, we have how many ways to achieve the sum.
The transitions will be
DP[k][sum] = case 1 +case 2
case 1 is not use the kth coin. It will be dp[k-1][sum] which is using the first k-1 coins to achieve the value sum.
case 2 is using the kth coin, it will be dp[k][sum-value of kth coin], as if we use the kth coin, we can move from the sum-value of kth coin to sum by using one kth coin as sum-value(k th coin) + value(k th coin)= sum.
We will have
DP[k][sum] = DP[k-1][sum]+DP[k][sum-value of kth coin]
The code of the second problem is an optimized one. If we use this naive 2D dp implementation, we will have the following code:
class Solution {
public:
int change(int amount, vector<int>& coins) {
int S=coins.size();
if (S==0)return int(amount==0);
vector<vector<int>> dp(S, vector<int>(amount+1));
//initialize the sum=0 case as 1.
for (int k=0;k<S;++k)dp[k][0]=1;
for (int k=0;k<S;++k){
int c = coins[k];
for (int sum=1;sum<=amount;++sum){
int case1, case2;
case1 = k-1<0?0:dp[k-1][sum];
case2 = sum-c<0?0:dp[k][sum-c];
dp[k][sum] = case1+case2;
}
}
return dp[S-1][amount];
}
};Relationship of the second problem to Knapsack problem
The second one is essentially a 0–1 Knapsack problem as in the Knapsack problem when considering the total weight, the order also doesn’t matter. So it is essentially a Knapsack problem.
