频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
求目标和的元素集合
2017-03-20 09:35:38      个评论      
收藏   我要投稿

求目标和的元素集合:可采用递归和分治的思想 和为target的结果 = ∑ni=0(和为target?candidates[i]的结果连接candidates[i]) 为了避免结果重复,遍历过程中,要去除已经存在的结果。

算法描述

对数组candidates升序排序 调用combinationSumOrder(vector& candidates, int target)递归实现
若candidates为空,则返回空; 遍历数组candidates:it
得到从it开始的新数组 candidates_new,得到新的目标值target_new 如果target_new <0 ,则返回空 如果target_new==0,则返回{*it} 如果target_new > 0,则执行combinationSumOrder(candidates_new,target_new),得到上一步的结果result_tmp; if result_tmp 不为空,则将result_tmp和*it拼接 再将result_tmp和result整合 得到result。

代码

//39. Combination Sum
vector> Solution::combinationSum(vector& candidates, int target)
{
    vector> result;
    if (candidates.empty())
        return result;
    sort(candidates.begin(), candidates.end());
    result = combinationSumOrder(candidates, target);
    return result;
}
vector> combinationSumOrder(vector& candidates, int target)
{
    // candidates 是有序的
    vector> result;
    if(candidates.empty())
        return result;
    const int n = candidates.size();
    for(auto it =candidates.begin(); it != candidates.end(); it++)
    {
        vector candidates_new(it,candidates.end());
        int target_new=target - *it;
        if(target_new == 0)
        {
            vector tmp;
            result.push_back({*it});
            break;
        }
        else if(target_new < 0)
        {
            break;
        }
        else 
        {
            vector> result_tmp = combinationSumOrder(candidates_new,target_new);
            if(result_tmp.empty())
                continue;
            for (int j = 0; j < result_tmp.size();j++)
            {
                result_tmp[j].insert(result_tmp[j].begin(),*it);
            }

            result.insert(result.end(),result_tmp.begin(),result_tmp.end());

        }       
    }
    return result;
}
点击复制链接 与好友分享!回本站首页
上一篇:CentOS7搭建DNS服务器
下一篇:tomcat端口被占用问题的解决(二)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站