leetcode 39. Combination Sum 、40. Combination Sum II 、216. Combination Sum III

时间：2022-03-18 08:11:11

Combination Sum:所有数都正数，原始数组中没有重复的数字，生成的子数组中可以重复使用某一个数值

Combination Sum II ： 所有数都正数，原始数组中有重复的数字，生成的子数组中不能重复使用某一个数值

Combination Sum III： 所有数都正数且只能是1到9之间的数，原始数组中没有重复的数字，生成的子数组中不能重复使用某一个数值

Combination Sum IV: 所有数都正数，原始数组中没有重复的数字，生成的子数组中可以重复使用某一个数值。但是这个不再是把所有的子数组找出来，而是找所有可能的子数组的个数。

39. Combination Sum

依旧与subsets问题相似，每次选择这个数是否参加到求和中。相对于subsets问题，增加一个target变量用于记录数值的和，并且result的push_back的条件也随之发生变化。

因为所有数字都是大于0的，所以target小于0就可以结束循环了。

因为是可以重复的，所以每次递归还是在i上，如果不能重复，就可以变成i+1。

class Solution {

public:

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        vector<vector<int>> result;

        vector<int> res;

        int length = candidates.size();

        if(length <= )

            return result;

        combination(candidates,result,res,target,);

        return result;

    }

    void combination(vector<int> candidates,vector<vector<int>> &result,vector<int> &res,int target,int start){

        if(target < )

            return;

        if(target == ){

            result.push_back(res);

        }

        for(int i = start;i < candidates.size();i++){

            res.push_back(candidates[i]);

            combination(candidates,result,res,target-candidates[i],i);

            res.pop_back();

        }

    }

};

https://www.jianshu.com/p/b2037dd2841a

类似于全排列和n皇后，用dfs形成一个n * m的matrix的遍历形式

40. Combination Sum II

与39题的不同在于：第一，本题有重复节点；第二，每个节点只能用一次，即没有自环

如何处理自环问题？每次搜索新路径的时候都从其下一个节点开始，而不是从它本身开始；

如何处理去重问题？每次回溯的时候，刚刚被剔除的节点不能在任何时候再被重新加入到路径上。如何处理这个“任何时候”呢？要么用map标记被剔除的节点直到路径搜索结束，要么应用排序，将所有有相同出权值的节点都放到一起, 通过排序就可以实现,这样可以方便找到下一个出权值不同的节点。

除了这两个部分，其他的与 Combination Sum一样。

class Solution {

public:

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

        vector<vector<int>> result;

        vector<int> res;

        int length = candidates.size();

        if(length <=  || target <= )

            return result;

        sort(candidates.begin(),candidates.end());

        combination(candidates,result,res,target,);

        return result;

    }

    void combination(vector<int> candidates,vector<vector<int>> &result,vector<int> &res,int target,int start){

        if(target < )

            return;

        if(target == ){

            result.push_back(res);

            return;

        }

        for(int i = start;i < candidates.size();i++){

            res.push_back(candidates[i]);

            combination(candidates,result,res,target-candidates[i],i+);

            res.pop_back();

            while(i < candidates.size() -  && candidates[i] == candidates[i+])

                i++;

        }

    }

};

http://www.cnblogs.com/tengdai/p/9257266.html

Combination Sum II是数组里面有重复的数字，但不像I那样允许你在你本身上进行重复，所以要用i+1

216. Combination Sum III

这个题与前两者不同的是，规定了组合的数字的个数，这样你就只能递归到第k层了，相当于在递归截止条件处要增加东西。

还有就是不再是一个输入的数组，而是直接1到9。原本发现需要把1到9输入到数组中，后来发现直接在递归里面写也是可以的。

class Solution {

public:

    vector<vector<int>> combinationSum3(int k, int n) {

        vector<vector<int> > result;

        if(k <=  || n <= )

            return result;

        vector<int> res;

        int start = ;

        combinationSum3(k,n,result,res,start);

        return result;

    }

    void combinationSum3(int k,int n,vector<vector<int> >& result,vector<int>& res,int start){

        if(n < )

            return;

        if(res.size() == k){

            if(n == )

                result.push_back(res);

            return;

        }

        for(int i = start;i <= ;i++){

            res.push_back(i);

            combinationSum3(k,n-i,result,res,i+);

            res.pop_back();

        }

    }

};

377. Combination Sum IV

这个题与39. Combination Sum 几乎一样，但是39. Combination Sum 是找所有可能的组合，这个题是找所有可能的子数组的个数，使用dfs也可以做，但在平台上会超时，采用dp的方式时间复杂度小。

dp[i]表示利用当前数组数字到数字i可以生成的个数。

class Solution {

public:

    int combinationSum4(vector<int>& nums, int target) {

        vector<unsigned int> dp(target + );

        dp[] = ;

        for(int i = ;i <= target;i++){

            for(int j = ;j < nums.size();j++){

                if(i - nums[j] >= )

                    dp[i] += dp[i - nums[j]];

            }

        }

        return (int)dp[target];

    }

};

注意：[3,33,333]
　　　10000

　　　这种情况，如果vector是int初始化，会报int相加越界的错误

http://www.cnblogs.com/grandyang/p/5705750.html

相关文章