LeeCode Combination Sum 剪枝回溯法的递归和非递归实现

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:

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Because it is not confined to a specific length of the answers, so we cannot kown that before testing, which means there are not fixed end point of the backtracking.

We have to prun(剪枝） the branch(分支）, and backtrack to the last number.

It work like this:

1 We sort the numbers in non-descendant way

排序

2 Add the smallest number first, and loop to add it again, and again, until we find a solution, or the solution's value is larger than our target number.

迭代或递归求解

3 We backtrack, by pop up the number , to the last number.

回溯

4 and then we try the next number in candidates, loop to 2.

The key thoughts to modle the solution are:

1 we use pushing number in and popping out to stand for backtracking thought.

回溯思想由push和pop体现

2 How many numbers in our solution stand for how deep level we iterate or recur.

3 we stop further iterate or recur by compare the number value in solution to the target number.

4 and further more, by knowing the way we arrange our candidates in a non-desendant way, we know if the current number won't fit for the answer, that the rest of the number in candidates won't fit too, so we don't need to try the rest. That's also the thought popular in AI, which call Heuristic Searching.

经验剪枝法

How we deal with repeated answers

We just forward trying, don't look back the numbers in candiates.

At first, I was wondering whether we can do it in a iterative(迭代循环）way.

So I try, and it work. Below is my iterative program:

	vector
  
    > combinationSum1(vector
   
     &candidates, int target) { sort(candidates.begin(), candidates.end()); vector
    
      intermediate; vector
     
       > result; vector
      
        indices; for (size_t i = 0; i < candidates.size(); ) { if(target <= candidates[i]) { //找到结果，保存，但是不入栈 if (target == candidates[i]) { intermediate.push_back(candidates[i]); result.push_back(intermediate); intermediate.pop_back(); } //注意：特殊情况-没有解或一个解，数字最小的值都大于等于target if(intermediate.empty()) return result; i = indices.back()+1; //注意：别忘了target也要恢复上一层的数值 target += intermediate.back(); intermediate.pop_back(); // 本层改数值不符合规定，或者已经找到了答案 indices.pop_back(); while (i == candidates.size()) {//别忘了这个情况 //注意：都需要判断空栈的时候返回值 if(intermediate.empty()) return result; i = indices.back()+1; target += intermediate.back(); intermediate.pop_back(); indices.pop_back(); } } else { intermediate.push_back(candidates[i]); indices.push_back(i); target -= candidates[i]; } } return result; }
      
     
    
   
  

But the program above is a little bit too complicate. And I think to a problem similar to this, we'd better use recursive way to solve it. So below is the recursive way.

http://discuss.leetcode.com/questions/61/combination-sum

	vector
  
    > combinationSum(vector
   
     &candidates, int target) { sort(candidates.begin(), candidates.end()); vector
    
      > result; // 最终结果 vector
     
       intermediate; // 中间结果 dfs(candidates, target, 0, intermediate, result); return result; } //不定深度的搜索，最好还是用递归 void dfs(vector
      
       & nums, int gap, int start, vector
       
        & intermediate, vector
        
          > &result) { if (gap == 0) { // 找到一个合法解 result.push_back(intermediate); return; } for (size_t i = start; i < nums.size(); i++) { // 扩展状态 //优化剪枝，如：{2,3,6,7} target=7;那么到了2,3之后7-2-3=4,nums[i]=6 //这样4<6那么6和7都不用继续下面的计算了，直接返回就可以了。 //这里是最好的剪枝位置了。 if (gap < nums[i]) return; // 剪枝 intermediate.push_back(nums[i]); // 执行扩展动作 dfs(nums, gap - nums[i], i, intermediate, result); intermediate.pop_back(); // 撤销动作 } }