LeetCode 39. Combination Sum 解题报告

题目描述

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.

示例

Example 1:

given candidate set [2, 3, 6, 7] and target 7.

solution is [[7], [2, 2, 3]].

注意事项

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

解题思路

我的思路：

这道题其实是考回溯，我习惯了用递归去做，整个过程当成了是一个深度搜索。枚举每一个元素作为根节点，然后每一个递归就添加一个新的节点，如果路径上的节点之和等于target就得到了一组结果，如果路径和大于target表示可以结束当前的搜索，返回上一层，尝试以下一个元素作为新节点的路径。最后返回得到的所有结果，需要注意的地方是递归结束返回后，需要把添加的节点去除，所以我的代码里在递归调用语句的前后分别有push_back跟pop_back。理解了算法的思想，整个过程其实很直观。

参考思路：

大神们的解法基本都是常规的回溯，当然，他们的实现始终比我要简洁，下面给出了他们的代码进行参考。

代码

我的代码：

class Solution {public:    void dfs(vector
   
    
     > &res, vector
     
      & c, vector
      
        comb, int t, int sum, int cur) {        for (int i = cur; i < c.size(); i++) {            sum += c[i];            comb.push_back(c[i]);            if (sum == t) {                res.push_back(comb);                return ;            } else if (sum > t) {                return;            }            dfs(res, c, comb, t, sum, i);            sum -= c[i];            comb.pop_back();        }    }    vector
       
        
         > combinationSum(vector
         
          & candidates, int target) { vector
          
           
            > res; vector
            
              comb; sort(candidates.begin(), candidates.end()); dfs(res, candidates, comb, target, 0, 0); return res; }};

参考代码：

class Solution {public:    vector
   
    
      > combinationSum(vector
     
       &candidates, int target) {        sort(candidates.begin(), candidates.end());        vector
      
       
         > res;        vector
        
          comb; combinationSum(candidates, target, res, comb, 0); return res; }private: void combinationSum(vector
         
           &cand, int target, vector
          
           
            > &res, vector
            
              &comb, int begin) { if (!target) { res.push_back(comb); return; } for (int i = begin; i != cand.size() && target >= cand[i]; ++i) { comb.push_back(cand[i]); combinationSum(cand, target - cand[i], res, comb, i); comb.pop_back(); } }};

总结

类似这种题目的问题有很多，一般都是把结果当作是叶子节点，中间状态作为中间节点，根据深搜的过程一边构建树一边求解，这只是我自己理解的一种方法，而经典的回溯问题还有N皇后问题，可以见我的这篇博客。

接下来两周都有考试，得认真复习了，然后到了7月份就得去网易游戏实习，未曾实习过的我开始觉得紧张了，趁还有时间要多准备准备，加油！

转载地址：http://mqntb.baihongyu.com/

你可能感兴趣的文章