LeetCode: Combination Sum I && II

I

给出一个集合，一个目标数字target，让你从集合中挑选出任意数字，其sum可以达到这个target，并且集合中的每个元素允许被多次重复选取。显然的NP问题，暴力深度优先搜索即可，几乎不用什么剪枝。注意添加答案的时候要注意判定重复，比较好的做法是另开一个set来去除重复，不过其实暴力也可以。

II

和上题类似，但是这题就需要小心一点了。一种朴素的想法是，对于集合中每一个数字，可以有两种状态：选中或者不选，这样直接对这两种状态可以DFS，但是效率会比较低，因为出现剪枝的情况会减少，总而言之，TLE。

我们可以考虑复杂度为阶乘的做法：每层递归都用循环，第一次选取0~n-1中的第i个，下次就要循环选取i+1~n-1中的元素，以此递归。有一个需要注意的地方，就是我们在同一层循环中，不要选择两个相同的元素同时向下递归，这样就保证了不会出现相同的答案，自然而然地完成了去重的工作，这个Trick需要仔细考虑。

代码

第一问

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    int dat[1000];
    vector<vector<int> > res;
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        res.clear();
        DFS(candidates, target, 0);
        return res;
    }

    void DFS( vector<int> &candidates, int target, int p )
    {
        if ( target == 0 ) {
            vector<int> cur;
            rep(i, p) cur.PB(dat[i]);
            sort(cur.begin(), cur.end());
            bool flag = true;
            rep(i, res.size()) if ( res[i] == cur ) flag = false;
            if ( flag ) res.PB(cur);
        }
        rep(i, candidates.size()) {
            if ( candidates[i] <= target ) {
                dat[p++] = candidates[i];
                DFS(candidates, target - candidates[i], p);
                p--;
            }
        }
    }
};

第二问

#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define rep(i,n) REP(i,0,n)
#define rev(i,n) REV(i,n,0)

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        VI cur;
        vector<VI> res;
        DFS(candidates, target, 0, cur, res);
        return res;
    }

    void DFS( vector<int> &candidates, int target, int pos, VI & cur, vector<VI> & res )
    {
        if ( target < 0 ) return;
        if ( target == 0 ) {
            res.PB(cur);
            return;
        }
        if ( pos >= candidates.size() ) return;
        REP(i, pos, candidates.size()) {
            if ( i > pos && candidates[i] == candidates[i - 1] ) continue;
            cur.push_back(candidates[i]);
            DFS(candidates, target - candidates[i], i + 1, cur, res);
            cur.pop_back();
        }
    }
};