? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?創(chuàng)作不易，感謝支持!!!

一、電話號(hào)碼的組合

. - 力扣（LeetCode）

class Solution {
public:
      string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
      string path;//記錄路徑
      vector<string> ret;//記錄返回值
    vector<string> letterCombinations(string digits) 
    {
        if(digits.size()==0) return ret;
        dfs(digits,0);
        return ret;
    }
    void dfs(string &digits,int pos)
    {
        if(path.size()==digits.size()) {ret.push_back(path);return;}
            for(auto ch:hash[digits[pos]-'0'])//從當(dāng)前位置開(kāi)始遍歷，然后再去下一個(gè)里面找
            {
                path.push_back(ch);
                dfs(digits,pos+1);
                path.pop_back();
            }
    }
};

二、括號(hào)生成

. - 力扣（LeetCode）

class Solution {
public:
    vector<string> ret;
    string path;
    int n;
    vector<string> generateParenthesis(int _n) 
    {
      n=_n;
      dfs(0,0);
      return ret;
    }
    void dfs(int open,int close)//open和close記錄上界和下界
    {
        if(path.size()==2*n) {ret.push_back(path);return;}
        if(open<n) 
        {
           path.push_back('(');
           dfs(open+1,close);
           path.pop_back();
        }
        if(close<open)
        {
           path.push_back(')');
           dfs(open,close+1);
           path.pop_back();
        }
    }
};

?三、組合

. - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int k;//用k全局，可以減少一個(gè)參數(shù)
    int n;//用n全局，可以減少一個(gè)參數(shù)
    vector<vector<int>> combine(int _n, int _k) 
    {
       k=_k;
       n=_n;
       dfs(1);
       return ret;
    }

    void dfs(int pos)
    {
        if(path.size()==k) {ret.push_back(path);return;}
        for(int i=pos;i<=n;++i)
        {
            path.push_back(i);
            dfs(i+1);
            path.pop_back();
        }
    }
};

四、目標(biāo)和

. - 力扣（LeetCode）

class Solution {
     int ret=0;//記錄返回結(jié)果
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        dfs(nums,target,0,0);
        return ret;
    }

    void dfs(vector<int>& nums, int target,int index,int sum)
    {
        if(index==nums.size()) 
        {
            if(sum==target)  ++ret;
        }
        //選正數(shù)
        else
        {
        dfs(nums,target,index+1,sum+nums[index]);
        dfs(nums,target,index+1,sum-nums[index]);
        }
    }
    
};

五、組合總和I

. - 力扣（LeetCode）

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        dfs(candidates,0,target);
        return ret;
    }

    void dfs(vector<int>& candidates,int pos,int target)
    {
     if(target==0){ ret.push_back(path);return;}
     if(target<0) return;
     for(int i=pos;i<candidates.size();++i)//第一層，遍歷每個(gè)數(shù)
      {
        path.push_back(candidates[i]);
        dfs(candidates,i,target-candidates[i]);//要從原先的位置去找
        path.pop_back();
      }
    }
};

class Solution {
    vector<vector<int>> ret;
    vector<int> path;
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        dfs(candidates,0,target);
        return ret;
    }

    void dfs(vector<int>& nums,int pos,int target)
    {
     if(target==0){ ret.push_back(path);return;}
     if(target<0||pos==nums.size()) return;
     for(int k=0;k*nums[pos]<=target;++k)//第一層，遍歷每個(gè)數(shù)
      {
        if(k) path.push_back(nums[pos]);
        dfs(nums,pos+1,target-k*nums[pos]);//要從原先的位置去找
      }
      for(int k=1;k*nums[pos]<=target;++k) path.pop_back();//

    }
};

六、組合總和II

. - 力扣（LeetCode）

七、組合總和III

. - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> ret;//記錄組合
    vector<int> path;//記錄路徑
    vector<vector<int>> combinationSum3(int k, int n) { 
        if(n>45) return ret;//剪枝
         dfs(k,n,1);
         return ret;
    }
    void dfs(int k,int n,int pos)
    {
        if(k==0&&n==0) 
        {
            ret.push_back(path);
            return;
        }
        if(n<0||k<0) return;
        for(int i=pos;i<=9;++i)
        {
            path.push_back(i);
            dfs(k-1,n-i,i+1);
            path.pop_back();
        }
    }
};

八、組合總和IV

. - 力扣（LeetCode）

該題和前面是類似的，但是用回溯算法，會(huì)超時(shí)

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int& num : nums) {
                if (num <= i&& dp[i - num] < INT_MAX - dp[i]) 
                {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-848361.html

到了這里，關(guān)于DFS：深搜+回溯+剪枝解決組合問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！