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

忘是亡心i 2022-09-14 08:36 213阅读 0赞

题目链接：[https://leetcode-cn.com/problems/combination-sum/][https_leetcode-cn.com_problems_combination-sum]  
题目如下：  
![在这里插入图片描述][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>> combinationSum(vector<int>& candidates, int target) {
        
    
            sort(candidates.begin(),candidates.end());
            dfs(candidates,target,0);
    
            return ans;
        }
    
        //表示当前在candidates数组的第start位，还剩target要组合，已经组合的列表为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){
        //从start位置开始向后遍历
                if(candidates[i]>target) break;//已排序，若>target，则直接跳出此次遍历，否则，就放入当前cur中
                else cur.push_back(candidates[i]);
    
                dfs(candidates,target-candidates[i],i);//从当前位置重新开始dfs，因为每个数字可以重复被选取
                cur.pop_back();//此时，弹出当前cur位置，继续下一个位置
            }
        }
    };

[https_leetcode-cn.com_problems_combination-sum]: https://leetcode-cn.com/problems/combination-sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/6807ad37287c47fbbfc77d322dcd38cb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8379626453be47a18d9f1c409b8fbe53.png