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

更新時(shí)間：2021年07月15日 08:58:33 作者：Grandyang

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

[LeetCode] 39. Combination Sum 組合之和

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

像這種結(jié)果要求返回所有符合要求解的題十有八九都是要利用到遞歸，而且解題的思路都大同小異，相類似的題目有 Path Sum II，Subsets II，Permutations，Permutations II，Combinations 等等，如果仔細(xì)研究這些題目發(fā)現(xiàn)都是一個套路，都是需要另寫一個遞歸函數(shù)，這里我們新加入三個變量，start 記錄當(dāng)前的遞歸到的下標(biāo)，out 為一個解，res 保存所有已經(jīng)得到的解，每次調(diào)用新的遞歸函數(shù)時(shí)，此時(shí)的 target 要減去當(dāng)前數(shù)組的的數(shù)，具體看代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> out;
        combinationSumDFS(candidates, target, 0, out, res);
        return res;
    }
    void combinationSumDFS(vector<int>& candidates, 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 < candidates.size(); ++i) {
            out.push_back(candidates[i]);
            combinationSumDFS(candidates, target - candidates[i], i, out, res);
            out.pop_back();
        }
    }
};

我們也可以不使用額外的函數(shù)，就在一個函數(shù)中完成遞歸，還是要先給數(shù)組排序，然后遍歷，如果當(dāng)前數(shù)字大于 target，說明肯定無法組成 target，由于排過序，之后的也無法組成 target，直接 break 掉。如果當(dāng)前數(shù)字正好等于 target，則當(dāng)前單個數(shù)字就是一個解，組成一個數(shù)組然后放到結(jié)果 res 中。然后將當(dāng)前位置之后的數(shù)組取出來，調(diào)用遞歸函數(shù)，注意此時(shí)的 target 要減去當(dāng)前的數(shù)字，然后遍歷遞歸結(jié)果返回的二維數(shù)組，將當(dāng)前數(shù)字加到每一個數(shù)組最前面，然后再將每個數(shù)組加入結(jié)果 res 即可，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        for (int i = 0; i < candidates.size(); ++i) {
            if (candidates[i] > target) break;
            if (candidates[i] == target) {res.push_back({candidates[i]}); break;}
            vector<int> vec = vector<int>(candidates.begin() + i, candidates.end());
            vector<vector<int>> tmp = combinationSum(vec, target - candidates[i]);
            for (auto a : tmp) {
                a.insert(a.begin(), candidates[i]);
                res.push_back(a);
            }
        }
        return res;
    }
};

我們也可以用迭代的解法來做，建立一個三維數(shù)組 dp，這里 dp[i] 表示目標(biāo)數(shù)為 i+1 的所有解法集合。這里的i就從1遍歷到 target 即可，對于每個i，都新建一個二維數(shù)組 cur，然后遍歷 candidates 數(shù)組，如果遍歷到的數(shù)字大于i，說明當(dāng)前及之后的數(shù)字都無法組成i，直接 break 掉。否則如果相等，那么把當(dāng)前數(shù)字自己組成一個數(shù)組，并且加到 cur 中。否則就遍歷 dp[i - candidates[j] - 1] 中的所有數(shù)組，如果當(dāng)前數(shù)字大于數(shù)組的首元素，則跳過，因?yàn)榻Y(jié)果要求是要有序的。否則就將當(dāng)前數(shù)字加入數(shù)組的開頭，并且將數(shù)組放入 cur 之中即可，參見代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<vector<int>>> dp;
        sort(candidates.begin(), candidates.end());
        for (int i = 1; i <= target; ++i) {
            vector<vector<int>> cur;
            for (int j = 0; j < candidates.size(); ++j) {
                if (candidates[j] > i) break;
                if (candidates[j] == i) {cur.push_back({candidates[j]}); break;}
                for (auto a : dp[i - candidates[j] - 1]) {
                    if (candidates[j] > a[0]) continue;
                    a.insert(a.begin(), candidates[j]);
                    cur.push_back(a);
                }
            }
            dp.push_back(cur);
        }
        return dp[target - 1];
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(39.組合之和)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)組合之和內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: