Recursive solution - correctly handling corner cases


  • 0
    A
    class Solution {
    public:
        void sol_update(vector<int>& sol, int k){
            for (int i = sol.size()-k; i < sol.size(); i++){
                sol[i] += 1;
            }
        }
        void helper(vector<vector<int>>& res, vector<int>& sol, int k, int n, int m){
            if (k*(k+1) > 2*n) return;
            if (k == 1){
                if (n <= m){
                    vector<int> sol_new(sol.begin(), sol.end());
                    sol_new[sol_new.size()-1] += n;
                    res.push_back(sol_new);
                    return;
                }
                else {
                    return;
                }
            }
            if (k > n){
                return;
            }
            vector<int> sol_new1(sol.begin(), sol.end());
            sol_update(sol_new1, k);
            helper(res, sol_new1, k-1, n-k, m-1);
            vector<int> sol_new2(sol.begin(), sol.end());
            sol_update(sol_new2, k);
            helper(res, sol_new2, k, n-k, m-1);
            return;
        }
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> res;
            vector<int> sol(k);
            for (int i = 0; i < k; i++){
                sol[i] = 0;
            }
            int m = 9;
            helper(res, sol, k, n, m);
            return res;
        }
    };
    

Log in to reply
 

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