力扣-40题组合总和 II（C++）- 回溯法+有价值

小鱼儿 2022-09-14 08:41 189阅读 0赞

思路详解见：[https://blog.csdn.net/qq\_40467670/article/details/120577321][https_blog.csdn.net_qq_40467670_article_details_120577321]  
此题是在这一题的基础上多了去重的操作。

题目链接：[https://leetcode-cn.com/problems/combination-sum-ii/][https_leetcode-cn.com_problems_combination-sum-ii]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
    public:
        vector<vector<int>> ans;
        vector<int> cur;
    
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
            sort(candidates.begin(),candidates.end());
            dfs(candidates,target,0);
    
            return ans;
        }
    
        void dfs(vector<int>& candidates,int target,int start){
        
            if(target==0){
        
                ans.push_back(cur);
                return ;
            }
    
            for(int i=start;i<candidates.size();++i){
        
                if(i>start&&candidates[i]==candidates[i-1]) continue;//important,去重固定套路，不是[i]==[i+1]
    
                if(candidates[i]>target) break;
    
                cur.push_back(candidates[i]);
                dfs(candidates,target-candidates[i],i+1);
                cur.pop_back();
            }
        }
    };

[https_blog.csdn.net_qq_40467670_article_details_120577321]: https://blog.csdn.net/qq_40467670/article/details/120577321
[https_leetcode-cn.com_problems_combination-sum-ii]: https://leetcode-cn.com/problems/combination-sum-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/da6a7bdbdb564bc7bf567d210b427743.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/b8d09ec50e2a4693a30627a2c9ed3451.png