Leetcode 39 Combination Sum

triplebee

发布于 2018-01-12 15:05:50

4760

发布于 2018-01-12 15:05:50

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.
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]
]

找出和为target的组合，每个数可重复使用，和POJ上一道搜索剪枝类似。

如果是求出所有组合的数量，肯定是DP，但是应为要求出具体组合，所以还是DFS好使。

注意剪枝条件：

1.排序，先搜大的，大的数可变性比较小，可以有效减少搜索空间

2.去除重复的数，这个也是在交完才发现的。

class Solution {
public:
    void dfs(vector<int>& candidates,int target,vector<vector<int>>& result,vector<int> path,int limit)
    {
        if(target==0)
        {
            result.push_back(path);    
            return ;
        }
        for(int i=candidates.size()-1;i>=0;i--)
        {
            if(candidates[i]>target || i>limit) continue;
            path.push_back(candidates[i]);
            dfs(candidates,target-candidates[i],result,path,i);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        vector<vector<int>> result;
        vector<int> path;
        sort(candidates.begin(),candidates.end());
        for(int i=0;i<candidates.size();i++)
            if(i<(candidates.size()-1) && candidates[i]==candidates[i+1])
            {
                candidates.erase(candidates.begin()+i);
                i--;
            }
        dfs(candidates,target,result,path,candidates.size()-1);
        return result;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-09-06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

combinations