【LeetCode】40. Combination Sum II

2019-11-06 07:34:35

字体：大中小

来源：转载

供稿：网友

题目描述

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]

解题思路

回溯法 + 剪枝。注意题目的与Combination Sum I的区别，这里的candidates是一个collection，元素有重复，但要求每个元素只能被使用一次。而I中的candidates是一个set，元素没有重复，但元素可以被重复使用。最终都是要求找到全部没有重复的组合。解决如下两个问题即可：

为了确保答案中没有重复，除了像I中要确保元素升序排序之外，还要确保每次跳过后面与之重复的元素为了确保每个元素只使用一次，只需将传入下次递归中的开始下标加一即可。

AC代码

class Solution {public: void bc(vector<vector<int>>& ans, vector<int>&cur, vector<int>& candidates, int target, int begin) { if (target == 0) { ans.push_back(cur); return; } for (int i = begin; i < candidates.size(); ++i) { if (candidates[i] <= target) { cur.push_back(candidates[i]); bc(ans, cur, candidates, target - candidates[i], i + 1); cur.pop_back(); int curNum = candidates[i]; while (i < candidates.size() && candidates[i] == curNum) i += 1; i -= 1; } } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); vector<vector<int>> ans; vector<int> cur; bc(ans, cur, candidates, target, 0); return ans; }};

上一篇：回文数

下一篇：跟：最大子序列问题

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注