Combination Sum

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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• 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]

Tags: array, backtracking

第一次在Linux下解题,还是直接在文本框里写,第一次落了一个分号,第二次_combinationSum拼成了_combinatonSum.两次编译没通过.修改后直接AC.

这次写的很慢,一步一步地检查.在提交前自己就发现了几个BUG.直接解决掉了.觉得慢写也有慢写的好处.一次就AC的感觉还是很爽的.

正文:

直接递归,然后剪枝.这里可以先对candidates进行升序排序.递归过程中可以pass掉一些元素,提升效率.

比较tricky的是它不允许重复的结果.这里我在递归函数_combinationSum中加入了一个参数start标记在candidates中循环的起点,以消除重复.

C++:

class Solution {
public:
    void _combinationSum(vector<vector<int> >& resultSet, vector<int>& currentResult, vector<int> & candidates, vector<int>::iterator start, int target){
        /**resultSet: the return value, final result
         * currentResult: current possible result. it's an element of final result.
         * candidates: sorted candidates value
         * start: start iterator of candidates. add this parameter to avoid duplicate results.
         * target: current target. It decreses by recursing, increases by backtracking.
         * BUG: Duplicate results.
         **/
        if (target == 0){
            //found a solution
            vector<int> re(currentResult);
            sort(re.begin(), re.end());
            resultSet.push_back(re);
            return;
        }
        else{
            //target > 0, continue to find a solution beneath current branch
            for(vector<int>::iterator it = start; it != candidates.end(); it++){
                if(*it > target){
                    //candidates are sorted in increasing order, if *it > target, all the following elements in candidates is bigger than target.
                    break;
                }
                else{
                    //push current element, go deeper
                    currentResult.push_back(*it);
                    _combinationSum(resultSet, currentResult, candidates, it, target - *it);
                    currentResult.pop_back();
                }
            }
        }
    }
    
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > resultSet;
        vector<int> currentResult;
        
        if(candidates.empty()){
            return resultSet;
        }
        
        sort(candidates.begin(), candidates.end());
        _combinationSum(resultSet, currentResult, candidates, candidates.begin(), target);
        
        return resultSet;
    }
};

程序运行效率