Combination Sum 系列

void Sum(int begin, vector<T> path, vector<T> candi, ...) {
	if(满足穷举结束条件) return;

	// 搜索一遍范围中的所有元素
	foreach(i=begin...N) {
		// 选择这个元素
		path.push_back(candi[i]);
		// Sum(..) 继续递归调用继续推进搜索
		path.pop_back(); // 回溯
	}
}

// Combination Sum
// 题目描述：待选择的数组是无重复的，但是允许重复选择
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        calSum(candidates, 0, target);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target) {
        if (!target) {
            res.push_back(path);
            return;
        }
		// 已排序的数组方便剪枝
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
            path.push_back(candi[i]);
            calSum(candi, i, target-candi[i]);
            path.pop_back();
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};

// Combination Sum II
// 题目描述：待选的数组是重复的，每个元素只能被选一次
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        calSum(candidates, 0, target);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target) {
        if (!target) {
            res.push_back(path);
            return;
        }
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
			// 已排序好的数组方便去重
            if (begin==i || candi[i] != candi[i-1]) {
                path.push_back(candi[i]);
                calSum(candi, i+1, target-candi[i]);
                path.pop_back();
            }
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};

// Combination Sum III
// 题目描述：只能从1到9中选择而且不允许重复选择
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> candi;
        for(int i=1;i<=9;++i) candi.push_back(i);
        calSum(candi, 0, n, k);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target, int k) {
        if (!target) {
            if (k==0) res.push_back(path);
            return;
        }
        if (!k) return;
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
            path.push_back(candi[i]);
            calSum(candi, i+1, target-candi[i], k-1);
            path.pop_back();
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};