C++實現(xiàn)LeetCode(40.組合之和之二)
[LeetCode] 40. Combination Sum II 組合之和之二
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
這道題跟之前那道 Combination Sum 本質沒有區(qū)別,只需要改動一點點即可,之前那道題給定數(shù)組中的數(shù)字可以重復使用,而這道題不能重復使用,只需要在之前的基礎上修改兩個地方即可,首先在遞歸的 for 循環(huán)里加上 if (i > start && num[i] == num[i - 1]) continue; 這樣可以防止 res 中出現(xiàn)重復項,然后就在遞歸調用 helper 里面的參數(shù)換成 i+1,這樣就不會重復使用數(shù)組中的數(shù)字了,代碼如下:
class Solution { public: vector<vector<int>> combinationSum2(vector<int>& num, int target) { vector<vector<int>> res; vector<int> out; sort(num.begin(), num.end()); helper(num, target, 0, out, res); return res; } void helper(vector<int>& num, int target, int start, vector<int>& out, vector<vector<int>>& res) { if (target < 0) return; if (target == 0) { res.push_back(out); return; } for (int i = start; i < num.size(); ++i) { if (i > start && num[i] == num[i - 1]) continue; out.push_back(num[i]); helper(num, target - num[i], i + 1, out, res); out.pop_back(); } } };
到此這篇關于C++實現(xiàn)LeetCode(40.組合之和之二)的文章就介紹到這了,更多相關C++實現(xiàn)組合之和之二內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!