33ms C++ Recursive Solution


  • 0
    A

    Other backtracking solutions proposed keep modifying the size of the current solution, which can result in bad performance due to relocations of the solution vector itself. In my proposal, the solution is represented as an array as long as the candidates, where each position represents the number of times the candidate is used in the solution. The only drawback is that we need a "translate" function to insert each new solution in the result, but the code is very clear and efficient IMHO:

    class Solution {
        typedef vector<int> VI;
        typedef vector<VI> VVI;
    public:
        VVI combinationSum(VI& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            VVI result;
            VI solution(candidates.size());
            combinationSumImpl(0, 0, solution, candidates, target, result);
            return result;
        }
    private:
        void combinationSumImpl(int i, int sum, VI& solution, const VI& candidates, int target, VVI& result) {
            int n = candidates.size();
            if (sum == target) addSolution(i, solution, candidates, result);
            else if (i < n && sum < target) {
                solution[i] = target/candidates[i];
                while (solution[i] >= 0) {
                    combinationSumImpl(i+1, sum+solution[i]*candidates[i], solution, candidates, target, result);
                    solution[i]--;
                }
            }
        }
        void addSolution(int i, const VI& solution, const VI& candidates, VVI& result) {
            VI tmp;
            for (int j = 0; j < i; ++j) {
                int count = solution[j];
                while (count > 0) {
                    tmp.push_back(candidates[j]);
                    --count;
                }
            }
            result.push_back(tmp);
        }
    };

  • 0
    K
    This post is deleted!

Log in to reply
 

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