dfs求组合数

这种题型套路比较固定，应该是比较好总结的，但是我自从昨天刚刚接触，我人已经麻了。

感觉对dfs的机理，以及何时开始调用，内部的执行顺序不会知道的非常透彻。

误打误撞了ac了leetcode的几道题，今天先mark一下。之后写的题目多了之后，我继续再总结。

—————————————————————-10.27—————————————————————

组合

77. 组合 - 力扣（LeetCode） (leetcode-cn.com)

题目非常简洁，只有两个参数，n与k。给一个1到n的范围，每一个组合有k个数，列举出所有的可能。

class Solution {
public:
    vector path ; 
    vector> res ; 
    
    vector> combine(int n, int k) {
        dfs(1 , 0 , n , k) ; 
        return res ; 
    }
    
    
    void dfs(int start , int u , int n , int k)
    {
        if(u == k)
        {
            res.push_back(path) ; 
            return  ; 
        }
        
        for(int i = start ; i <= n  ; ++ i)
        {
            path.push_back(i) ; 
            dfs(i+1 , u +1 , n , k) ;
            path.pop_back() ; 
        }
    }
    return  ; 
};

组合总和

39. 组合总和 - 力扣（LeetCode） (leetcode-cn.com)

y总的思路，u的含义是遍历candidate数组的每一个下标。对每一个下标而言，用一个循环判断需要使用多少个该元素,对于每一轮改变target的值，恢复现场即可。

贴个代码：

class Solution {
public:
    vector ans ; 
    vector> res ; 
    
    
    vector> combinationSum(vector& candidates, int target) {
        dfs(0 , candidates , target) ; 
        return res ; 
    }
    
    void dfs(int u , vector candidates , int target)
    {
        if(target == 0)
        {
            res.push_back(ans) ; 
            return  ;
        }
        
        if(u == candidates.size())
        {
            return  ; 
        }
        
        for(int i = 0 ; i * candidates[u] <= target ; ++ i)
        {
            dfs(u + 1 , candidates , target - i * candidates[u]) ; 
            ans.push_back(candidates[u]) ; 
        }
        
        for(int i = 0 ; i * candidates[u] <= target ; ++ i)
        {
            ans.pop_back() ; 
        }
     return ;    
    }
};

组合总和II

40. 组合总和 II - 力扣（LeetCode） (leetcode-cn.com)

与上面一题的区别是，数组中有了重复元素，但是只能用已有的元素，就是将个数限定死了，不是想上面一题类似于完全背包问题。

我们只需要在找数量的时候，加一条限制，不超过所给的数量即可。但是有一点要注意，要进行去重，否则答案会出现很多重复答案。

贴个代码：

class Solution {
public:
    vector ans ;
    vector> res ;
    unordered_map ha ; 
    
    vector> combinationSum2(vector& candidates, int target) {
        sort(candidates.begin() , candidates.end()) ; 
        for(int num : candidates)
        {
            ha[num] ++ ; 
        }
        candidates.erase(unique(candidates.begin() , candidates.end()) , candidates.end()) ; 
        dfs(0 , candidates , target) ;
        return res ; 
    }
    
    void dfs(int u , vector candidates ,int target)
    {
        if(target == 0)
        {
            res.push_back(ans) ; 
            return  ; 
        }
        
        if(u == candidates.size())
        {
            return ; 
        }
        
        for(int i = 0 ; i * candidates[u] <= target && i <= ha[candidates[u]] ; ++ i)
        {
            dfs(u+1 , candidates , target - i * candidates[u]) ; 
            ans.push_back(candidates[u]) ;         
        }
        for(int i = 0 ; i * candidates[u] <= target && i <= ha[candidates[u]] ; ++ i)        
        {
            ans.pop_back() ; 
        }
        return ; 
    }
};

组合总和III

216. 组合总和 III - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    vector ans ;
    vector> res ; 
    
    
    vector> combinationSum3(int k, int n) {
        dfs(1 , 0 , k , n) ;
        return res ; 
    }
    
    void dfs(int start , int u , int k , int n)
    {
        if(u == k)
        {
            int num = accumulate(ans.begin() , ans.end() , 0) ; 
            if(num == n)
            {
                res.push_back(ans) ; 
                return  ; 
            }
        }
           for(int i = start ; i <= 9; ++ i)
        {
            if(i > n)
                return  ; 
            ans.push_back(i) ; 
            dfs(i + 1 , u + 1 , k , n ) ; 
            ans.pop_back() ; 
        }
        return ; 
    }
};