18 lines shortest C++ code, sort then backtracking, very easy to understand


  • 2
    class Solution {
        void combine(const vector<int>& cand, int idx, int target, vector<int> &path, vector<vector<int>>&res){
             for( ;idx<cand.size() && cand[idx] <= target ; ++idx){
                 path.push_back(cand[idx]);
                 if(cand[idx] == target) res.push_back(path);
                 else combine(cand, idx, target - cand[idx], path, res);
                 path.pop_back();
             }
        }
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
             sort(candidates.begin(), candidates.end());
             vector<vector<int>> res;
             vector<int> path;
             combine(candidates, 0, target, path, res);
             return res;
        }
    };
    

  • 0
    L

    Very good and clean solution!
    Thanks!


  • 0
    B

    does not check the duplication.


Log in to reply
 

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