Recursive C++ Solution, FYI


  • 0
    A
    class Solution {
    public:
        void helper(vector<vector<int>>& res, vector<int>& sol, int target, vector<int>& candidates){
            if (target == 0){
                res.push_back(sol);
            }
            if (candidates.size() == 0){
                return;
            }
            else if (target < candidates[0]){
                return;
            }
            else {
                int head = candidates[0];
                int i = 0;
                vector<int> dup_sol(sol.begin(), sol.end());
                while ((candidates[i] == head) && i < candidates.size()){
                    i++;
                }
                vector<int> sub_cands(candidates.begin()+i, candidates.end());
                int n = 0;
                vector<int> sol0(dup_sol.begin(), dup_sol.end());
                helper(res, sol0, target, sub_cands);
                while (n < i){
                    dup_sol.push_back(head);
                    vector<int> sol00(dup_sol.begin(), dup_sol.end());
                    helper(res, sol00, target-(n+1)*head, sub_cands);
                    n++;
                }
            }
            return;
        }
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<vector<int>> res;
            vector<int> sol;
            helper(res, sol, target, candidates);
            return res;
        }
    };
    

Log in to reply
 

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