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)文章

簡(jiǎn)單解讀C++中的虛函數(shù)
這篇文章主要介紹了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)來(lái)封裝wchar_t與char類(lèi)型間的轉(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)建與銷(xiāo)毀原理圖解
我們知道c語(yǔ)言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過(guò)本文給大家分享c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷(xiāo)毀過(guò)程，一起看看吧
2022-05-05
C++虛函數(shù)表和虛析構(gòu)介紹
這篇文章主要介紹了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