LeetCode 40 Combination Sum II

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

题意：

集合中的每个数字只能使用一次，求出所有数字和为target的方案。

思路：

如果把集合中的数字计数，问题会变得和 http://blog.csdn.net/houserabbit/article/details/72677176 几乎一致。

我的方法思路与计数思路几乎一致，只不过我没有合并数字，而是枚举每种数字个数的时候只取排在后面的数字，这样就保证了方案不重复。

代码：

class Solution {
public:vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {n = candidates.size();count = new int[n];vector<vector<int>> ans;sort(candidates.begin(), candidates.end());dfs(n - 1, target, ans, candidates);return ans;}private:int n;int *count;void dfs(int idx, int target, vector<vector<int>> &ans, vector<int> &candidates) {if (candidates[idx] <= target &&(idx == n - 1 || candidates[idx] != candidates[idx + 1] || count[idx + 1] == 1)) {count[idx] = 1;int newtar = target - candidates[idx];if (newtar == 0) {vector<int> res;for (int i = idx; i < n; ++i) {if (count[i] == 1) {res.push_back(candidates[i]);}}ans.push_back(res);} else if (idx > 0) {dfs(idx - 1, newtar, ans, candidates);}}count[idx] = 0;if (idx > 0) {dfs(idx - 1, target, ans, candidates);}}
};

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

---