LeetCode第40题之Combination Sum II

本文主要是介绍LeetCode第40题之Combination Sum II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这一题主要是在上一题的基础上解决重复解的问题。
C++代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Solution {
private://res保存满足题意的结果vector<vector<int>> res;//保存当前的一种方案vector<int> method;
public:void fun(int n, int sum, vector<int> &candidates, int target, vector<int> &method, vector<vector<int>> &res){if (target == sum){res.push_back(method);return;}for (int i=n;i<candidates.size();++i){//同一层次不能出现相同的元素if (i>n && candidates[i] == candidates[i-1])continue;//剪枝if (candidates[i]+sum > target)return;method.push_back(candidates[i]);fun(i+1, sum+candidates[i], candidates, target, method, res);method.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());fun(0, 0, candidates, target, method, res);return  res;}
};int main()
{Solution s;vector<int> canditates;canditates.push_back(10);canditates.push_back(1);canditates.push_back(2);canditates.push_back(7);canditates.push_back(6);canditates.push_back(1);canditates.push_back(5);vector<vector<int>> res = s.combinationSum2(canditates, 8);for (vector<vector<int>>::iterator ita=res.begin();ita!=res.end();++ita){for (vector<int>::iterator itb=ita->begin();itb!=ita->end();++itb){cout<<*itb<<'\t';}cout<<endl;}cout<<endl;return 0;
}

这篇关于LeetCode第40题之Combination Sum II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---