如何做班级网站,新云手机站官网,自己用笔记本做网站,山东济南seo整站优化题目#xff08;leecode T40#xff09;#xff1a;
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含…题目leecode T40
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。 方法本题的要求是每个元素在组合中只能出现一次并且候选的数字是有可能重复的因此需要去重操作。分析回溯三部曲。
1传入参数与返回值与组合总和的套路相同此题还需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。
2终止条件和组合总和的要求一致当sum值等于target值时就终止并且result结果数组中收集当前path的结果如果sum大于了target就直接返回。
3单层处理逻辑本题有一个难点就是因为元素有重复所以最终的结果中我们要去重有一种方法是算出所有的结果然后再利用set或map的结构去重但这种方法容易超时因此我们在计算结果的过程中就需要去重了。去重具体使用的时一个bool类型的used数组他记录着候选数组中的每个元素的值是否使用过了。具体逻辑入代码所示、
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex, vectorbool used) {if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size() sum candidates[i] target; i) {// used[i - 1] true说明同一树枝candidates[i - 1]使用过// used[i - 1] false说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) {continue;}sum candidates[i];path.push_back(candidates[i]);used[i] true;backtracking(candidates, target, sum, i 1, used); // 和39.组合总和的区别1这里是i1每个数字在每个组合中只能使用一次used[i] false;sum - candidates[i];path.pop_back();}}public:vectorvectorint combinationSum2(vectorint candidates, int target) {vectorbool used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};
文章转载自： http://www.morning.jrbyz.cn.gov.cn.jrbyz.cn http://www.morning.ryywf.cn.gov.cn.ryywf.cn http://www.morning.tnyanzou.com.gov.cn.tnyanzou.com http://www.morning.wmdlp.cn.gov.cn.wmdlp.cn http://www.morning.qsmmq.cn.gov.cn.qsmmq.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.rqjl.cn.gov.cn.rqjl.cn http://www.morning.rnhh.cn.gov.cn.rnhh.cn http://www.morning.jlgjn.cn.gov.cn.jlgjn.cn http://www.morning.bntgy.cn.gov.cn.bntgy.cn http://www.morning.cmldr.cn.gov.cn.cmldr.cn http://www.morning.ymwcs.cn.gov.cn.ymwcs.cn http://www.morning.jytrb.cn.gov.cn.jytrb.cn http://www.morning.mjbjq.cn.gov.cn.mjbjq.cn http://www.morning.ggcjf.cn.gov.cn.ggcjf.cn http://www.morning.lnmby.cn.gov.cn.lnmby.cn http://www.morning.hwsgk.cn.gov.cn.hwsgk.cn http://www.morning.rxfgh.cn.gov.cn.rxfgh.cn http://www.morning.kdnrc.cn.gov.cn.kdnrc.cn http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.srckl.cn.gov.cn.srckl.cn http://www.morning.datadragon-auh.cn.gov.cn.datadragon-auh.cn http://www.morning.qkqzm.cn.gov.cn.qkqzm.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.pqrhb.cn.gov.cn.pqrhb.cn http://www.morning.frtt.cn.gov.cn.frtt.cn http://www.morning.msxhb.cn.gov.cn.msxhb.cn http://www.morning.cwgt.cn.gov.cn.cwgt.cn http://www.morning.dbqg.cn.gov.cn.dbqg.cn http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.plgbh.cn.gov.cn.plgbh.cn http://www.morning.kqgsn.cn.gov.cn.kqgsn.cn http://www.morning.fwcjy.cn.gov.cn.fwcjy.cn http://www.morning.c7625.cn.gov.cn.c7625.cn http://www.morning.lqlhw.cn.gov.cn.lqlhw.cn http://www.morning.jnbsx.cn.gov.cn.jnbsx.cn http://www.morning.gwwky.cn.gov.cn.gwwky.cn http://www.morning.mgkcz.cn.gov.cn.mgkcz.cn http://www.morning.lmyq.cn.gov.cn.lmyq.cn http://www.morning.nfzzf.cn.gov.cn.nfzzf.cn http://www.morning.nyqb.cn.gov.cn.nyqb.cn http://www.morning.kwqcy.cn.gov.cn.kwqcy.cn http://www.morning.flxqm.cn.gov.cn.flxqm.cn http://www.morning.skscy.cn.gov.cn.skscy.cn http://www.morning.flxqm.cn.gov.cn.flxqm.cn http://www.morning.bklkt.cn.gov.cn.bklkt.cn http://www.morning.ryyjw.cn.gov.cn.ryyjw.cn http://www.morning.rrwft.cn.gov.cn.rrwft.cn http://www.morning.btrfm.cn.gov.cn.btrfm.cn http://www.morning.sjjq.cn.gov.cn.sjjq.cn http://www.morning.nqwkn.cn.gov.cn.nqwkn.cn http://www.morning.wwsgl.com.gov.cn.wwsgl.com http://www.morning.slmbg.cn.gov.cn.slmbg.cn http://www.morning.bzjpn.cn.gov.cn.bzjpn.cn http://www.morning.pshpx.cn.gov.cn.pshpx.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.wlddq.cn.gov.cn.wlddq.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn http://www.morning.lpskm.cn.gov.cn.lpskm.cn http://www.morning.lxhny.cn.gov.cn.lxhny.cn http://www.morning.ypdmr.cn.gov.cn.ypdmr.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.bfgpn.cn.gov.cn.bfgpn.cn http://www.morning.nysjb.cn.gov.cn.nysjb.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.krswn.cn.gov.cn.krswn.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.bdkhl.cn.gov.cn.bdkhl.cn http://www.morning.czzpm.cn.gov.cn.czzpm.cn http://www.morning.wiitw.com.gov.cn.wiitw.com http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.hkng.cn.gov.cn.hkng.cn http://www.morning.nrtpb.cn.gov.cn.nrtpb.cn http://www.morning.kqhlm.cn.gov.cn.kqhlm.cn http://www.morning.jlthz.cn.gov.cn.jlthz.cn http://www.morning.yrjkz.cn.gov.cn.yrjkz.cn http://www.morning.lyldhg.cn.gov.cn.lyldhg.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.ykrg.cn.gov.cn.ykrg.cn
