Tuesday, February 3, 2015

LeetCode [39] Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
Accepted
334,599
Submissions
695,146
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
class Solution
{
  public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        int sz = candidates.size();
        vector<vector<int>> ret;
        bt(0, sz, ret, 0, target, vector<int>(), candidates);
        return ret;
    }

    void bt(int pos, int sz, vector<vector<int>> &ret, int currentSum, int target, vector<int> vec, vector<int> &candidates)
    {
        if (currentSum == target)
        {
            ret.push_back(vec);
            return;
        }

        if (pos == sz)
            return;

        //do not choose num at "pos"
        bt(pos + 1, sz, ret, currentSum, target, vec, candidates);

        //choose num for 1, 2, 3 ... times until the sum exceeds target

        while (currentSum + candidates[pos] <= target)
        {
            vec.push_back(candidates[pos]);
            currentSum += candidates[pos];
            bt(pos + 1, sz, ret, currentSum, target, vec, candidates);
        }
    }
};

//legendary code
//C++: method1 200ms
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        int n = candidates.size();
        if(!n) return res;
        sort(candidates.begin(), candidates.end());
        vector<int> cur;
        bt(candidates, n, target, 0, res, cur, 0);
        return res;
    }

    void bt(vector<int>& candidates, int n, int target, int pos, vector<vector<int>> &res, vector<int> cur, int sum){
        if(sum==target){
            res.push_back(cur);
        }else if(sum<target && pos<n){
            bt(candidates, n, target, pos+1, res, cur, sum);
            int d = candidates[pos];
            sum += d;
            cur.push_back(d);
            bt(candidates, n, target, pos, res, cur, sum);
        }
    }
};
]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: method2 188ms
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        vector<vector<int>> ret;
        sort(candidates.begin(), candidates.end());
        vector<int> cur;
        helper(candidates, target, 0, cur, ret, 0, n);
        return ret;
    }

    void helper(vector<int>& candidates, int target, int pos, vector<int> cur, vector<vector<int>> &ret, int sum, int n){
        if(sum==target){
            ret.push_back(cur);
            return;
        }
        if(pos>=n||sum>target) return;
        int v = candidates[pos];
        int i = pos+1;//next number different than v
        while(i<n && candidates[i]==v) ++i;
        helper(candidates, target, i, cur, ret, sum, n);
        while(sum<target){
            cur.push_back(v);
            sum += v;
            helper(candidates, target, pos+1, cur, ret, sum, n);
        }
    }
};

]]></script>

<script class="brush: js" type="syntaxhighlighter"><![CDATA[
//C++: method3 20ms
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        bt(candidates, target, ret, cur, 0, 0, n);
        return ret;
    }
    void bt(vector<int>& candidates, int target, vector<vector<int>> &ret, vector<int> cur, int pos, int sum, int n){
        if(sum==target){
            if(!cur.empty()) ret.push_back(cur);
        }else if(sum<target && pos<n){
            for(int i=pos; i<n; ++i){
                if(sum+candidates[i]>target) return;
                cur.push_back(candidates[i]);
                bt(candidates, target, ret, cur, i, sum+candidates[i], n);
                cur.pop_back();
            }
        }
    }
};
Posted by at
Labels: , , , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)