leetcode39. 組み合わせの合計、40.組合せ総和II(c++)

目次

組合せ合計

題

構想

コード

組合せ総和II

題

構想

コード

コンビネーション合計
タイトル
重複要素のない配列candidatesとターゲット数targetを指定し、candidatesのすべての数値とtargetの組合せを見つけます.candidatesの数字は、無制限に繰り返し選択できます.説明:targetを含むすべての数値は正の整数です.解セットに重複する組合せを含めることはできません.例1:入力:candidates=[2,3,6,7],target=7,解法セット:[[7],[2,2,3]]例2:入力:candidates=[2,3,5],target=8,解法セット:[[2,2,2,2,2],[2,3,3],[3,5]
構想
一般的に、すべての組合せ状況をリストする必要がある問題は、深さ優先パスで解決できます.すなわち、1つのパスを最後まで探して、前のレイヤに戻って最後まで歩き続け、すべての状況をパスするまで、プロセスで状況に合致するレコードを記録して戻ります.この問題は組合せを見つけてtargetと等しいので、数字は繰り返し使用することができるので、1つの数を選択するたびにtarget-現在の下付きラベルに対応する値を譲って、それから得られた数を0に等しいまで伝えて、つまり1つの組合せを見つけて、順次再帰します.
コード#コード#

class Solution {
public:
    void dfs(vector>& ans,vector &candidates,vector &tmp,int target,int start)//      ，start     
    {
        if(target<0)//      ，  
        {
            return;
        }
        else if(target==0)//  ，  ans 
        {
            ans.push_back(tmp);
            return;
        }
        else
        {
            for(int i=start;i> combinationSum(vector& candidates, int target) 
    {
        vector> ans;//   
        vector tmp;//    
        if(candidates.empty())//  ，  
        {
            return ans;
        }
        sort(candidates.begin(),candidates.end());//         
        dfs(ans,candidates,tmp,target,0);//dfs
        return ans;
    }
};

組合せ合計II
タイトル
配列candidatesとターゲット数targetを指定し、candidatesのすべての数値とtargetの組合せを見つけます.candidatesの各数字は、各組合せで1回しか使用できません.説明:すべての数値(ターゲット数を含む)は正の整数です.解セットに重複する組合せを含めることはできません.例1:入力:candidates=[10,1,2,7,6,1,5],target=8,解セット:[[1,7],[1,2,5],[2,6],[1,1,6]]例2:入力:candidates=[2,5,2,2],target=5,解セット:[[1,2,[5],[5]
構想
この問題と前の問題の違いは、数字ごとに繰り返してはいけないし、繰り返してはいけないということです.全体的な考え方は前の問題と似ていて、同じ値をフィルタリングするだけでいいです.
コード#コード#

class Solution {
public:
    
    void dfs(vector>& ans,vector& candidates,vector& tmp,int target,int start)
    {
        if(target==0)
        {
            ans.push_back(tmp);
            return;
        }
        else if(target < 0)
        {
            return;
        }
        else
        {
            for(int i=start;i> combinationSum2(vector& candidates, int target) 
    {
        vector> ans;
        vector tmp;
        
        if(candidates.empty())
            return ans;
        
        sort(candidates.begin(),candidates.end());
        dfs(ans,candidates,tmp,target,0);
        return ans;
    }
};