leetcode组合总和

leetcode组合总和

1.递归+回溯

首先有3点需要注意:

1)数组中的元素可能有重复的

2)数组中的每个元素在每个组合中只能使用一次

3)解集中不能存在重复集合

所以,需要考虑去重

首先进行排序,

其次,去重考虑当前元素与前一个元素是否相等,如果相等,说明将其放在当前位置的排列已经记录,则跳过

代码如下:

class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        //递归+回溯
        //数组中的每一个元素只能使用一次
         vector<int> ans;
         sort(candidates.begin(),candidates.end());
         getSum(candidates,ans,0,target);
        return res;
    }
     void getSum(vector<int>&c,vector<int> &ans,int start,int target)
    {
        if(target==0)
        {
              res.push_back(ans);
              return ;
        }
        for(int i=start;i<c.size();i++)
        {
            if(target-c[i]>=0)
            {
            if(i>start&&c[i]==c[i-1])
              continue;//去重,当前原数组与前一个元素相等,则跳过
            ans.push_back(c[i]);
            getSum(c,ans,i+1,target-c[i]);
            ans.pop_back();
            }
            else
              break;
        }
    }
};

 

上一篇:40-组合总和2


下一篇:leetcode 39. Combination Sum