題目

Given a set of candidate numbers (C) (without duplicates) 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.
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]
]

分析

最簡單的思路，就是通過對target減去candidates中的一個數(shù)來得到一個子問題。通過遞歸求解即可。還需要解決的一點是，這種方法會導致重復，所以需要在最后加入一個去重的部分，首先對每個解法中的數(shù)字排序，然后對所有解排序，最后去重得到結果。

實現(xiàn)一

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        ans = solve(candidates, target);
        for(int i=0; i<ans.size(); i++){
            sort(ans[i].begin(), ans[i].end());
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        return ans;
    }
private:
    vector<vector<int>> solve(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        for(auto num: candidates){
            if(target-num<0){
                continue;
            }
            else if(target-num==0){
                ans.push_back({num});
            }
            else{
                vector<vector<int>> tmp;
                tmp = solve(candidates, target-num);
                if(tmp.empty())
                    continue;
                for(auto v: tmp){
                    v.push_back(num);
                    ans.push_back(v);
                }
            }
        }
        return ans;
    }
};

思考一

這種方法固然可行，但是由于重復的存在，會導致效率偏低。所以著手考慮優(yōu)化。對每個子問題的解都進行去重可以縮短一部分時間，但是效果不是很明顯。
較好的改進方法是，在遞歸的下一步時，只使用candidates中大于等于上一個使用的數(shù)字，這樣就能保證所得的序列是遞增的，也能保證其不重復。這樣大大減少了運算時間。

實現(xiàn)二

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        ans = solve(candidates, target, 0);/*
        for(int i=0; i<ans.size(); i++){
            sort(ans[i].begin(), ans[i].end());
        }
        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());*/
        return ans;
    }
private:
    vector<vector<int>> solve(vector<int>& candidates, int target, int start) {
        vector<vector<int>> ans;
        for(int i=start; i<candidates.size(); i++){
            if(target-candidates[i]<0){
                continue;
            }
            else if(target-candidates[i]==0){
                ans.push_back({candidates[i]});
            }
            else{
                vector<vector<int>> tmp;
                tmp = solve(candidates, target-candidates[i], i);
                if(tmp.empty())
                    continue;
                for(auto v: tmp){
                    v.push_back(candidates[i]);
                    ans.push_back(v);
                }
            }
        }
        return ans;
    }
};