Combination Sum

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背包和可重复背包）有什么相似之处吗？


留言

▲