DFS：深搜+回溯+剪枝解决组合问题

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'])//从当前位置开始遍历，然后再去下一个里面找
            {
                path.push_back(ch);
                dfs(digits,pos+1);
                path.pop_back();
            }
    }
};

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();
        }
    }
};

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int k;//用k全局，可以减少一个参数
    int n;//用n全局，可以减少一个参数
    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();
        }
    }
};

class Solution {
     int ret=0;//记录返回结果
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;
        }
        //选正数
        else
        {
        dfs(nums,target,index+1,sum+nums[index]);
        dfs(nums,target,index+1,sum-nums[index]);
        }
    }
    
};

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)//第一层，遍历每个数
      {
        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)//第一层，遍历每个数
      {
        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();//

    }
};

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();
        }
    }
};

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];
    }
};