首页 > 代码库 > Combination Sum 和Combination Sum II
Combination Sum 和Combination Sum II
这两道题的基本思路和combination那一题是一致的，也是分治的方法。
其中combination Sum复杂一点，因为每个数可能用多次。仔细分析下，本质上也是一样的。原来是每个数仅两种可能。现在每个数有k +１中可能，k = target / i。
所以就是把简单的if else 分支变成for循环：
vector<vector<int> > combHelper(vector<int>::iterator first, vector<int>::iterator last, int target){ vector<vector<int>> result; if (target <= 0 || last == first) return result; if (*(last - 1) == target){ vector<int> vi; vi.push_back(target); result.push_back(vi); auto r2 = combHelper(first, last - 1, target); for (auto it = r2.begin(); it != r2.end(); it++) result.push_back(*it); } else if (*(last - 1) < target){ auto r1 = combHelper(first, last - 1, target - *(last - 1)); for (auto it = r1.begin(); it != r1.end(); it++){ it->push_back(*(last - 1)); result.push_back(*it); } auto r2 = combHelper(first, last - 1, target); for (auto it = r2.begin(); it != r2.end(); it++) result.push_back(*it); } else { auto r2 = combHelper(first, last - 1, target); for (auto it = r2.begin(); it != r2.end(); it++) result.push_back(*it); } return result;}vector<vector<int> > combinationSum2(vector<int> &num, int target) { sort(num.begin(), num.end()); auto result = combHelper(num.begin(), num.end(), target); if (!result.empty()){ sort(result.begin(), result.end()); auto it = unique(result.begin(), result.end()); result.erase(it, result.end()); } return result;}
Combination Sum 和Combination Sum II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。