C++實(shí)現(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 本質(zhì)沒有區(qū)別,只需要改動(dòng)一點(diǎn)點(diǎn)即可,之前那道題給定數(shù)組中的數(shù)字可以重復(fù)使用,而這道題不能重復(fù)使用,只需要在之前的基礎(chǔ)上修改兩個(gè)地方即可,首先在遞歸的 for 循環(huán)里加上 if (i > start && num[i] == num[i - 1]) continue; 這樣可以防止 res 中出現(xiàn)重復(fù)項(xiàng),然后就在遞歸調(diào)用 helper 里面的參數(shù)換成 i+1,這樣就不會(huì)重復(fù)使用數(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(); } } };
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(40.組合之和之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)組合之和之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實(shí)現(xiàn)LeetCode(52.N皇后問題之二)
- C++實(shí)現(xiàn)LeetCode(50.求x的n次方)
- C++實(shí)現(xiàn)LeetCode(49.群組錯(cuò)位詞)
- C++實(shí)現(xiàn)LeetCode(48.旋轉(zhuǎn)圖像)
- C++實(shí)現(xiàn)LeetCode(43.字符串相乘)
- C++實(shí)現(xiàn)LeetCode(41.首個(gè)缺失的正數(shù))
- C++實(shí)現(xiàn)LeetCode(144.二叉樹的先序遍歷)
- C++實(shí)現(xiàn)LeetCode(58.求末尾單詞的長度)
相關(guān)文章
利用C語言實(shí)現(xiàn)經(jīng)典游戲斗獸棋
《斗獸棋》是一款棋類游戲,整個(gè)游戲畫面是分為兩塊區(qū)域,中間有河流分割兩塊區(qū)域,有橋梁可以讓彼此的動(dòng)物過河,要取得勝利,必須占領(lǐng)那一邊動(dòng)物的巢穴獲勝利。本文將用C語言實(shí)現(xiàn)這一游戲,需要的可以參考一下2022-03-03