Accepted 12ms, Very Simple Backtracking solution


  • 0
    N
    class Solution {
        void combinationSum(vector<int> &input, int startIdx, int& target, int& sum, vector<int>& current, vector<vector<int>>& res) {
            if (sum == target) {
                res.push_back(current);
                return;
            }
            for (int i = startIdx; i < input.size(); ++i) {
                sum += input[i];
                if (sum > target) {
                    sum -= input[i];
                    break;
                }
                current.push_back(input[i]);
                combinationSum(input, i, target, sum, current, res);
                sum -= input[i];
                current.pop_back();
            }
        }
    
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> res;
            vector<int> current;
            int sum = 0;
            sort(candidates.begin(), candidates.end());
            combinationSum(candidates, 0, target, sum, current, res);
            return res;
        }
    };
    

    Here I am sorting the input, so to prune entries quickly


Log in to reply
 

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