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ì)沒(méi)有區(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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C++實(shí)現(xiàn)LeetCode(52.N皇后問(wè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.二叉樹(shù)的先序遍歷)
- C++實(shí)現(xiàn)LeetCode(58.求末尾單詞的長(zhǎng)度)
相關(guān)文章
這篇文章主要介紹了C++中的虛函數(shù),在C++中,虛函數(shù)聯(lián)系到多態(tài)、多態(tài)聯(lián)系到繼承,因而虛函數(shù)是C++中的一大重要特性,需要的朋友可以參考下2016-04-04
C++多字節(jié)字符與寬字節(jié)字符相互轉(zhuǎn)換
最近在C++編程中經(jīng)常遇到需要多字節(jié)字符與寬字節(jié)字符相互轉(zhuǎn)換的問(wèn)題，自己寫(xiě)了一個(gè)類來(lái)封裝wchar_t與char類型間的轉(zhuǎn)換2012-11-11
c++實(shí)現(xiàn)MD5算法實(shí)現(xiàn)代碼
用c++實(shí)現(xiàn)了md5算法。包含 md5.h 和md5.cpp 兩個(gè)文件。主要參考百度百科 “MD5” 原理，代碼中變量命名也是參考其中的公式，程序的使用說(shuō)明在md5.h 文件的末尾注釋中2013-11-11
C語(yǔ)言 經(jīng)典題目螺旋矩陣 實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言 經(jīng)典題目螺旋矩陣 實(shí)例詳解的相關(guān)資料,這里附有代碼實(shí)例及實(shí)現(xiàn)效果圖，需要的朋友可以參考下2016-12-12
C語(yǔ)言函數(shù)棧幀的創(chuàng)建與銷毀原理圖解
我們知道c語(yǔ)言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過(guò)本文給大家分享c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷毀過(guò)程，一起看看吧2022-05-05
這篇文章主要介紹了C++虛函數(shù)表和虛析構(gòu)，虛函數(shù)表是C++實(shí)現(xiàn)多態(tài)的基礎(chǔ)，多態(tài)是面向?qū)ο蟮娜筇匦灾?，下面文章我們一起?lái)看看詳細(xì)內(nèi)容,需要的朋友可以參考一下2021-11-11
模擬實(shí)現(xiàn)C語(yǔ)言中的內(nèi)存管理
這篇文章主要內(nèi)容是模擬C語(yǔ)言中的內(nèi)存管理,需要的朋友可以參考下2015-07-07
C語(yǔ)言動(dòng)態(tài)內(nèi)存管理的實(shí)現(xiàn)示例
動(dòng)態(tài)內(nèi)存管理是一種允許程序在運(yùn)行時(shí)根據(jù)需要?jiǎng)討B(tài)申請(qǐng)和回收內(nèi)存的策略,它提供了四種重要的函數(shù),本文就來(lái)介紹一下,感興趣的可以了解一下2024-11-11
Linux下用C語(yǔ)言實(shí)現(xiàn)推箱子游戲
這篇文章主要為大家詳細(xì)介紹了Linux下用C語(yǔ)言實(shí)現(xiàn)小老鼠推箱子的游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
詳解C語(yǔ)言對(duì)字符串處理函數(shù)的實(shí)現(xiàn)方法
這篇文章主要為大家介紹了C語(yǔ)言對(duì)字符串處理函數(shù)的實(shí)現(xiàn)方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12