39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

---

本题要从一个集合中取出一些数，使得和为某个特定的数target，输出所有的这种组合。注意不能有重复的组合，比如[2,2,3]和[3,2,2]算是重复的。

这是很常见的组合问题，使用递归的思路求解。比如样例，要求和为7，则每个加数必须小于等于7，所以依次尝试2,3,6,7，如果是2，则还差7-2=5，所以递归的在[2,3,6,7]里面找和为5的组合。如此递归，直到差为0。但是这样有一个问题，比如你这一次尝试的是2，则可能得到[2,2,3]的组合，下一次尝试3，则可能得到[3,2,2]的组合，但是这两个组合是相同的。我一开始的想法是对组合排序，然后用set去重。代码如下：

class Solution {
public:
    void work(set<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
    {
        if (target == 0) {
            vector<int> tmp = sol;
            sort(tmp.begin(), tmp.end());
            ans.insert(tmp);
        }
        else {
            for (int i = 0; i < candidates.size(); i++) {
                if (candidates[i] > target)
                    break;
                sol.push_back(candidates[i]);
                work(ans, candidates, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        set<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, sol, target);
        return vector<vector<int> >(ans.begin(), ans.end());
    }
};

本代码提交AC，但是用时145MS，只击败了4.5%的人，所以肯定还有更优的方案。

上述方案的一个费时的地方就是要对每个组合排序，然后用set去重，如果能省掉这个环节，速度会快很多。

网上查看题解之后，恍然大悟，每次只选不小于上一次选过的数，这样得到的组合就不会有重复，不需要排序，也不需要set去重。比如上面的例子，在选到3时，差7-3=4，此时再从[2,3,6,7]里面选时，只选大于等于3的数，也就是3,6,7，不再考虑2了。但是6,7都大于4，不行；3的话，剩余4-3=1也无解。所以搜3的时候，就不会得到[3,2,2]的结果，也就无需去重。
完整代码如下：

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidates, vector<int>& sol, int target)
    {
        if (target == 0) {
            ans.push_back(sol);
        }
        else {
            for (int i = 0; i < candidates.size(); i++) {
                if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() – 1]))
                    continue;
                sol.push_back(candidates[i]);
                work(ans, candidates, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, sol, target);
        return ans;
    }
};

本代码提交AC，用时20MS，速度快了好多。

后来我发现这个版本的代码还可以优化，因为candidates已经排好序了，如果这次取了i号元素，下一次只要取i及以后的元素即可，所以在递归的时候多传入一个下标值，也能提速。完整代码如下：

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& candidates, int idx, vector<int>& sol, int target)
    {
        if (target == 0) {
            ans.push_back(sol);
        }
        else {
            for (int i = idx; i < candidates.size(); i++) {
                if (candidates[i] > target)
                    break;
                sol.push_back(candidates[i]);
                work(ans, candidates, i, sol, target – candidates[i]);
                sol.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum(vector<int>& candidates, int target)
    {
        vector<vector<int> > ans;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        work(ans, candidates, 0, sol, target);
        return ans;
    }
};

本代码提交AC，用时16MS。

二刷。没必要排序，直接DFS选当前及后续元素即可，代码如下：

class Solution {
public:
	void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
		if (target == 0) {
			ans.push_back(cur);
			return;
		}
		if (target < 0)return;
		for (int i = idx; i < candidates.size(); ++i) {
			target -= candidates[i];
			cur.push_back(candidates[i]);
			dfs(candidates, target, ans, cur, i);
			cur.pop_back();
			target += candidates[i];
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> cur;
		dfs(candidates, target, ans, cur, 0);
		return ans;
	}
};

本代码提交AC，用时12MS。