快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(40.組合之和之二)

更新時(shí)間：2021年07月15日 11:10:32 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(40.組合之和之二),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

C語(yǔ)言編程C++編輯器及調(diào)試工具操作命令詳解
這篇文章主要介紹了C語(yǔ)言編程C++編輯調(diào)試工具操作命令詳解，本文章對(duì)C++調(diào)試工具的命令操作進(jìn)行了詳細(xì)的講解，有需要的朋友可以借鑒參考下
2021-09-09
詳解C++11中的右值引用與移動(dòng)語(yǔ)義
本篇文章主要介紹了詳解C++11中的右值引用與移動(dòng)語(yǔ)義，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
2017-02-02
利用C語(yǔ)言實(shí)現(xiàn)經(jīng)典游戲斗獸棋
《斗獸棋》是一款棋類游戲，整個(gè)游戲畫(huà)面是分為兩塊區(qū)域，中間有河流分割兩塊區(qū)域，有橋梁可以讓彼此的動(dòng)物過(guò)河，要取得勝利，必須占領(lǐng)那一邊動(dòng)物的巢穴獲勝利。本文將用C語(yǔ)言實(shí)現(xiàn)這一游戲，需要的可以參考一下
2022-03-03
C語(yǔ)言中的鏈接編寫(xiě)教程
這篇文章主要介紹了C語(yǔ)言中的鏈接編寫(xiě)教程,是C語(yǔ)言入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
2015-08-08
C++內(nèi)存池的簡(jiǎn)單實(shí)現(xiàn)
內(nèi)存池是一種動(dòng)態(tài)內(nèi)存分配與管理技術(shù)。本文主要介紹了C++內(nèi)存池的簡(jiǎn)單實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2021-07-07
VScode platformio使用的詳細(xì)步驟
使用VSCode作為編輯器,同時(shí)借助PlatformIO插件,可以幫助開(kāi)發(fā)者更加高效地進(jìn)行嵌入式開(kāi)發(fā),本文主要介紹了VScode platformio使用的詳細(xì)步驟,感興趣的可以了解一下
2023-10-10
12個(gè)關(guān)于C語(yǔ)言的有趣問(wèn)答
這篇文章主要介紹了12個(gè)關(guān)于C語(yǔ)言的有趣問(wèn)答,有助于讀者加深對(duì)C語(yǔ)言程序設(shè)計(jì)的理解,需要的朋友可以參考下
2014-07-07
深入解析C++編程中的靜態(tài)成員函數(shù)
這篇文章主要介紹了深入解析C++編程中的靜態(tài)成員函數(shù),是C++入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
2015-09-09
C++11智能指針unique_ptr用法使用場(chǎng)景分析
unique_ptr 是 C++ 11 提供的用于防止內(nèi)存泄漏的智能指針中的一種實(shí)現(xiàn)，即使在異常發(fā)生時(shí)也可幫助避免資源泄露。這篇文章主要介紹了C++11智能指針unique_ptr用法介紹,需要的朋友可以參考下
2021-08-08
C++深入分析講解類的知識(shí)點(diǎn)
C++類，是指系統(tǒng)在第一次在程序中遇到一個(gè)類時(shí)為這個(gè)類建立它的所有類變量的拷貝 - 這個(gè)類的所有實(shí)例共享它的類變量
2022-06-06