Accepted 16ms c++ solution use backtracking, easy understand.


  • 128

    Accepted 16ms c++ solution use backtracking for Combination Sum:

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

    Accepted 12ms c++ solution use backtracking for Combination Sum II:

    class Solution {
    public:
        std::vector<std::vector<int> > combinationSum2(std::vector<int> &candidates, int target) {
            std::sort(candidates.begin(), candidates.end());
            std::vector<std::vector<int> > res;
            std::vector<int> combination;
            combinationSum2(candidates, target, res, combination, 0);
            return res;
        }
    private:
        void combinationSum2(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {
            if (!target) {
                res.push_back(combination);
                return;
            }
            for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i)
                if (i == begin || candidates[i] != candidates[i - 1]) {
                    combination.push_back(candidates[i]);
                    combinationSum2(candidates, target - candidates[i], res, combination, i + 1);
                    combination.pop_back();
                }
        }
    };
    

    Accepted 0ms c++ solution use backtracking for Combination Sum III:

    class Solution {
    public:
        std::vector<std::vector<int> > combinationSum3(int k, int n) {
            std::vector<std::vector<int> > res;
            std::vector<int> combination;
            combinationSum3(n, res, combination, 1, k);
            return res;
        }
    private:
        void combinationSum3(int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin, int need) {
            if (!target) {
                res.push_back(combination);
                return;
            }
            else if (!need)
                return;
            for (int i = begin; i != 10 && target >= i * need + need * (need - 1) / 2; ++i) {
                combination.push_back(i);
                combinationSum3(target - i, res, combination, i + 1, need - 1);
                combination.pop_back();
            }
        }
    };
    

  • 0
    T

    There is a litter problem in your code for Combination Sum.if the input is [2,2],target is 4.your
    code's result is [2,2],[2,2] ,[2,2].This contain duplicate combinations.


  • 3

    [2,2] is not a valid input for candidates because 2 is a duplicate. Please see the problem description again carefully: Given a set of candidate numbers (C)


  • 0
    P

    What does "i * need + need * (need - 1) / 2" means?


  • 0

    target >= i + (i+1) + ... + (i +need-1) = i * need + need * (need - 1) / 2;

    You can also written as follows:

    int end = (target - need * (need - 1) / 2) / need;
    if (end > 9 - need + 1)
        return;
    for (int i = begin; i <= end; ++i) {
    	combination.push_back(i);
    	combinationSum3(target - i, res, combination, i + 1, need - 1);
    	combination.pop_back();
    }

  • 9
    P

    Combination Sum III

    class Solution {
    public:
        void combination(int k, int n, vector<int>& v, vector<vector<int>>& ret, int beg){
            if(k == 0 && n == 0){
                ret.push_back(v);
                return;
            }
            for(int i = beg; i < 10 && i <= n; i++){
                v.push_back(i);
                combination(k - 1, n - i, v, ret, i + 1);
                v.pop_back();
            }
        }
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> ret;
            vector<int> v;
            combination(k, n, v, ret, 1);
            return ret;
        }
    };

  • 0
    P

    I see. You are right! I have posted my code below.


  • 6
    R

    Hi
    Can someone tell me complexity of the solution ?


  • 2
    S

    What's the complexity?


  • 0
    S

    Combination Sum III:

    void helper(int k, int target, vector<vector<int>>&r, vector<int>&temp, int pos) {
        if (target == 0 && temp.size() == k)
        {       
            r.push_back(temp);
            return;
        }
        for (int i = pos; i <= 9; i++)
        {
            if (target >= i)
            {
                temp.push_back(i);
                helper(k, target - i, r, temp, i + 1);
                temp.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>>r;
        vector<int>temp;
        helper(k, n, r, temp, 1);
        return r;
    }

  • 0
    K

    I am trying to figure it out as well. Please let us know if anyone came up with an idea.


  • 0
    R

    Is time complexity O(n^2) ?


  • 1
    S

    First of all, thanks a lot for the answer.

    My questions is that, reading a few of the top rated solution with dfs/backtracking approach, I'm wonder why no one yet exploited the fact that some of the 'subtrack' would have been 'visited' already.

    e.g. if target=4, candidates=[1,2] - the ‘subtrack’ below (target-candidates[i]=2) would have been ‘visited’ more than once hence can be ‘reused’ using caching. (A bit trickier than that, we need to use only the part of the ’subtrack’ where subtrack[0] >= candidates[i] to avoid duplicate)


  • 0
    P

    Weird. The problem states:

    • The solution set must not contain duplicate combinations.

    Your code for Combination Sum doesn't handle the case with duplicates, but surprisingly it gets accepted by the judge.

    I tried input 2,2,3,6,7and it returned [[2,2,3],[2,2,3],[2,2,3],[7]] which is what the OJ expects, but that's wrong based on the description, the correct answer should be [[2,2,3],[7]]

    Am I missing something?

    UPDATE: Sorry just re-read the description and the input is set, so ignore this comment.


  • 0
    H
    This post is deleted!

  • 0
    S

    There will be no this kind of problem by "&& target >= candidates[i]" in loop statement.


  • 0
    C

    I have a question, In "combination sum", why should we pop_back? I don't understand for a long time.Can anyone explain it?


  • 1
    S

    @cheffyu that's so called backtracking.


  • 0
    F

    I think your third solution is not easy to grasp and remember. Here is better version I think

    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> result;
            vector<int> out;
            help(k, n, 1, out, result);
            return result;
        }
        
        void help(int k, int n, int level, vector<int>& out, vector<vector<int>>& result) {
            if (n < 0) return;
            if (n == 0 && k == out.size()) result.push_back(out);
            for (int i = level; i <= 9; i++) {
                out.push_back(i);
                help(k, n - i, i + 1, out, result);
                out.pop_back();
            }
        }
    };

  • 1
    R

    What does combination.pop_back() do exactly? Can someone please explain this to me.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.