Combination Sum I, II （C++ code）

LeetCode Combination Sum, Mar 7 '12
难度3，出现频率3
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]
思路： 基础的排列组合题。因为一个数可取多次，所以iteration的时候起点还是从当前点开始算。注意下面的code要求candidate set里无重复数字。

void findpath(vector<vector<int>> &res, int level, int cursum, vector<int> &path, int target, vector<int> &cand){
   if(cursum > target) return;
   if(cursum == target){
      res.push_back(path);
      return;
   }

   for(int i = level; i < cand.size(); i++){
      path.push_back(cand[i]);
      cursum += cand[i];
      findpath(res, i, cursum, path, target, cand);
      cursum -= cand[i];
      path.pop_back();
   }  
}

vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
 vector< vector<int>> res;
 if(candidates.empty()) return res;
 vector<int> path;
 int cursum = 0;
 sort(candidates.begin(), candidates.end());
 findpath(res,0,0,path, target, candidates);

 return res;
}

Combination Sum II， Mar 7 '12
难度4，出现频率2
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 (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 10,1,2,7,6,1,5 and target 8,

思路： 类似上面一题，只是一个元素只能用一次，递归时应从i+1开始，另外此题可能candidate set有重复元素，在递归时记得去掉。例如
[1 1 1 2 2]
当第一个1循环完后，要去掉第二和第三个1,同理第一个2循环完后去掉第二个2.

void findpath(vector<vector<int>> &res, int level, int cursum, vector<int> &path, int target, vector<int> &cand){

   if(cursum > target) return;

   if(cursum == target){
      res.push_back(path);
      return;
   }

   for(int i = level; i < cand.size();){
      path.push_back(cand[i]);
      cursum += cand[i];
      findpath(res, i+1, cursum, path, target, cand);
      cursum -= cand[i];
      path.pop_back(); 
//erase duplicate elements before proceeding.
      i++;
      while(i<cand.size() && cand[i-1] == cand[i]) i++;
   }

}

vector<vector<int> > combinationSum2(vector<int> &num, int target) {
 vector< vector<int>> res;
 if(num.empty()) return res;
 vector<int> path;
 int cursum = 0;
 sort(num.begin(), num.end());
 findpath(res,0,0,path, target, num);

 return res;
}