39. Combination Sum

January 24, 2017

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.

Note:

  • All numbers (including target) will be positive integers.
  • 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]
]

Description

本题要求从一个不重复序列中挑选出若干求和后与target相等的子序列,要求是每个元素可被选择无限次且返回的集合中不能有重复元素。

Analysis

典型的回溯法的应用,递归过程中,需要将每次的求和结果与目标值之间的差距作为参数来回传递,此外,由于能够使用之前用过的元素,所以在搜索过程中和以前的DFS算法也有所不同,具体体现在:递归调用时,递归深度并不+1,代码如下:

code

class Solution {
    void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
        if(remain<0)      return;
        if(remain==0){
            res.push_back(temp);
            return;
        }
        for(int i=start;i<candidates.size();++i){
            temp.push_back(candidates[i]);
            backtracking(res,temp,candidates,remain-candidates[i],i);//notice here
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
        vector<int> temp;
        vector<vector<int>> res;
        backtracking(res,temp,candidates,target,0);
        return res;
    }
};

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017