Combination sum 1 and 2 是 Leetcode 上面两道比较相似的题目。今天写这个题目是因为这个题目有不同的解法。

这两道题目都是给定一组数,给定一个 target,然后求出这组数中哪几个可以组合成 target。不同的地方是,第一道题要求数字可以被重复利用以组合成 target;第二道题要求数字不可以被重复利用。Seems easy, hmm?

首先说说我的想法和做法。首先通过观察可以得知,求一个 target 的 combination 可以被拆分成给定某个已知数的剩下数值的 combination 的子问题。于是乎,可以在确定一个 candidate 的同时试图解决这个子问题,子问题应该返回一个所有解的列表,把该 candidate 加入所有解的尾部即可。

那么怎么选取 candidate 呢?我们可以先对原候选数组进行排序,从最接近 target 的最大数开始筛选 candidate。

但是这里面还有不少问题。在解决子问题的时候,父问题应该传递给子问题这样的信息,使得子问题在选择 candidate 的时候,不应该出现重复的解。比如说在数组[2,3,6,7],target 为 7 的时候,当目前确定一个 candidate 为 2,子问题就是相同数组中 target 为 5 的问题。但是此时是否能选择 candidate 为 3 呢?这就与 target 为 7 时 candidate 选为 3 的时候相重复了啊。为了力避这种情况,我规定父问题必须传给子问题当前的 candidate,使得子问题在选择 candidate 之时永远小于父问题 candidate。

所以解决问题的代码如下:

Combination Sum I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
sort(candidates.begin(),candidates.end());
return dfs(candidates,target,INT_MAX);
}
vector<vector<int> > dfs(vector<int> &candidates, int target, int pred){
vector<int>::const_iterator itr;
vector<vector<int> > ans;
itr = upper_bound(candidates.begin(), candidates.end(), target);
if(itr==candidates.begin()) return ans;
do{
itr--;
int t = *itr;
if(t>=pred) continue;
if(!(target%t)) ans.push_back(vector<int>(target/t,t));
for(int i=1; i<=target/t; i++){
vector<vector<int> > vst = dfs(candidates, target-i*t, t);
for(size_t j=0; j!=vst.size(); j++)
for(int k=0; k!=i; k++) vst[j].push_back(t);
copy(vst.begin(), vst.end(), back_inserter(ans));
}
}while(itr!=candidates.begin());
return ans;
}
};

下面第二道题,第一道题之后应该不是什么难题,因为所有的数只能选择一次,所以在选择 candidate 的时候用不着去尝试多次选取的情况了。但是这里还有一个问题:位置不同、但是“看上去”结果相同的解被算作同一个!

为了优雅地解决这个问题,我规定在选取下一个 candidate 的时候,需要跳过与目前 candidate 相同的值。(注意第 22 行)

所以这个问题解决的代码如下:

Combination Sum II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());
return dfs(candidates.rbegin(),candidates.rend(),target);
}
vector<vector<int> > dfs(vector<int>::const_reverse_iterator b, vector<int>::const_reverse_iterator e,
int target){
vector<int>::const_reverse_iterator itr;
vector<vector<int> > ans;
itr = upper_bound(b,e,target,greater_equal<int>());
if(itr==e) return ans;
while(itr!=e){
int t = *itr;
if(t==target) ans.push_back(vector<int>(1,t));
vector<vector<int> > vs = dfs(++itr, e, target-t);
for(size_t i=0; i!=vs.size(); i++){
vs[i].push_back(t);
ans.push_back(vs[i]);
}
while(itr!=e && *itr==t) itr++;
}
return ans;
}
};

但是,以上这些方法都是沿用了 dfs 的思想。既然问题能被拆分为子问题,那么为何不用 DP?这当然是一个正当的思路。

我们记 target 从 0 到 target 的所有解的数组为 dp[target+1],最终的结果就是要求 dp[target]。显然我们有 dp[target]=vector({itm.push_back(candidate) for itm in dp[target-i]})(抱歉这种不伦不类的语法)

但是状态转移方程还没有明确从哪里取得 candidate。其实只要从所有 candidate 里面一个一个抽取出来就可以了。

所以说解决第一题的伪代码如下:

Combination Sum I in DP
1
2
3
4
5
dp[0]=vector<vector<int>>()
for c in candidates:
for j in [c, target]:
如dp[j-c]非空:
dp[j] = 把dp[j-c]中的每一个解都push_back一个c

对于第二题用 DP 的话必须配合 Hash set。

另外,您发现了,用 dp 解的话与背包问题(0-1背包和可重复背包)有什么相似之处吗?


留言