[leetcode] Combination Sum and Combination SumII

Given a set of candidate numbers (C) 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.
• Elements in a combination (a1, a2,
  … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤
  … ≤ ak).
• 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]

class Solution {

private:

    vector<vector<int> > ivvec;

public:

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {

        vector<int> ivec;

        sort(candidates.begin(), candidates.end());

        combinationSum(candidates, 0, target, ivec);

        return ivvec;

    }

    void combinationSum(vector<int> &candidates, int beg, int target, vector<int> ivec)

    {

        if (0 == target)

        {

            ivvec.push_back(ivec);

            return;

        }

        for (int idx = beg; idx < candidates.size(); ++idx)

        {

            if (target - candidates[idx] < 0)

                break;

            ivec.push_back(candidates[idx]);

            combinationSum(candidates, idx, target - candidates[idx], ivec);

            ivec.pop_back();

        }

    }

};

Given a collection of candidate numbers (C)
and a target number (T), find all unique combinations in C where
the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2,
  … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤
  … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8 ,

A solution set is:

[1, 7]

[1, 2, 5]

[2, 6]

[1, 1, 6]

与上题差别不大。依然是用DFS，基本的问题在于怎样去重。

能够添加一个剪枝: 当当前元素跟前一个元素是同样的时候。假设前一个元素被取了，那当前元素能够被取，也能够不取，反过来假设前一个元素没有取。那我们这个以及之后的所以同样元素都不能被取。

(採用flag的向量作为标记元素是否被选取)

class Solution {

private:

    vector<vector<int> > ivvec;

    vector<bool> flag;

public:

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {

        vector<int> ivec;

        sort(num.begin(), num.end());

        flag.resize(num.size());

        for (int i = 0; i < flag.size(); ++i)

            flag[i] = false;

        combinationSum2(num, 0, ivec, target, 0);

        return ivvec;

    }

    void combinationSum2(vector<int> &num, int beg, vector<int> ivec, int target, int sum)

    {

        if (sum > target)

            return;

        if (sum == target)

        {

            ivvec.push_back(ivec);

            return;

        }

        for (int idx = beg; idx < num.size(); ++idx)

        {

            if (sum + num[idx] > target) continue;

            if (idx != 0 && num[idx] == num[idx - 1] && flag[idx - 1] == false)

                continue;

            flag[idx] = true;

            ivec.push_back(num[idx]);

            combinationSum2(num, idx + 1, ivec, target, sum + num[idx]);

            ivec.pop_back();

            flag[idx] = false;

        }

    }

};