即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

【LeetCode】Combination Sum

编程语言 xiazhiyiyun 22℃ 0评论
本文目录
[隐藏]

1.Combination Sum

1.1.【LeetCode】39.Combination Sum

1.1.1.介绍

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

1.1.2.解答

解析:

回溯算法。或者是DFS。与之类似的问题有数据的全排列。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> one;
        sort(candidates.begin(),candidates.end());
        combinationSumActu(candidates,target,0,one,res);
        return res;
    }
private:
    void combinationSumActu(const vector<int> & candidates,int target,int begin,vector<int> & one,vector<vector<int>> & res)
    {
        if(target == 0)
        {
            res.push_back(one);
            return;
        }
        for(int i = begin; i < candidates.size() && target >= candidates[i]; ++i)
        {
            one.push_back(candidates[i]);
            combinationSumActu(candidates,target-candidates[i],i,one,res);
            one.pop_back();
        }
    }
};

1.2.【LeetCode】 40. Combination Sum II

1.2.1.介绍

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.

The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,


A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

题意:和39.Combination Sum相似,但是区别在于,数组中可能存在重复的元素,并且每个元素只能使用一次。得到的结果集也不应该重复。

1.2.2.解答

仍然采用回溯法,但是注意每个元素只能使用一次,所以每次递归过程中begin的值都是当前下标加1。并且要注意跳过重复的元素。防止得到重复的结果集合。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<int> one;
        vector<vector<int>> res;
        helper(candidates,target,0,one,res);
        return res;
    }

private:    
    void helper(const vector<int> & candidates,int target,int begin,vector<int> & one,vector<vector<int>> & res)
    {
        if(target == 0)
        {
            res.push_back(one);
            return;
        }
        for(int i = begin; i < candidates.size() && target >= candidates[i]; ++i)
        {
            one.push_back(candidates[i]);
            helper(candidates,target-candidates[i],i+1,one,res);
            one.pop_back();
            // 跳过重复的结点
            while(i+1 < candidates.size() && candidates[i+1] == candidates[i])
                ++i;
        }
    }
};

1.3.【LeetCode】216. Combination Sum III

1.3.1.介绍

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

与前两题类似,依旧采用回溯法,但是要注意,题意中要求正好是k个元素来组成目标数字n。

1.3.2.解答

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        if(k <= 0 || n <= 0)
            return res;
        vector<int> one;
        helper(k,n,1,one,res);
        return res;
    }
private:  
    void helper(int k,int target,int begin,vector<int> &one,vector<vector<int>> &res)
    {
        if( k== 0)
        {
            if(target == 0) res.push_back(one);
            return;
        }
        for(int i = begin; i < 10 && target >= i; ++i)
        {
            one.push_back(i);
            helper(k-1,target-i,i+1,one,res);
            one.pop_back();
        }
    }
};

转载请注明:CodingBlog » 【LeetCode】Combination Sum

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情