C++ Recursion + backtracking with explanation


  • 0
    C

    Here we use the cSum function as recursive function with additional input like minVal (the minimum value we can put now) and current is the current building vector so far.

    In this function, the first thing I check is if there's no way we can continue building our vector, like n < k * minVal or minVal > 9 or n > k*9. The next thing to check is if k = 1, in that case we only need to push n to the current vector (if n < 10). Other wise, we start pushing value from minVal to 9 to the current vector and call cSum recursively with the update minVal and current vector.

    It seems like we have some redundant work here which can be utilized by Dynamic Programming. For example if the current vector is <1,5> or <2,4>, it seems like the remaining work of these 2 cases are the same. In fact, it is quite different since the minVal for the first case is 6 while the minVal for the 2nd case is 5. Overall, we have some overlapping work but might be hard to use DP here.

    Any comments and suggestions are welcome.

    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int> > res;
            if (k == 0 || k > 9) return res; // Check easy cases first
            vector<int> current;
            return cSum(k, n, 1, current);
        }
        
        vector<vector<int> > cSum(int k, int n, int minVal, vector<int> &current){
            vector<vector<int> > res;
            if (n < k * minVal || minVal > 9 || n > k*9) return res; // Also check easy cases
            if (k == 1) { // base case where k = 1
                if (n > 9) return res; 
                current.push_back(n);
                res.push_back(current);
                current.pop_back(); // back track
                return res;
            }
            for (int val = minVal; val < 10; val++){
                current.push_back(val);
                vector<vector<int> > tmp = cSum(k-1, n-val, val+1, current);
                if (tmp.empty()) {
                    current.pop_back(); // back track
                    continue;
                }
                for (int i = 0; i < tmp.size(); i++){
                    res.push_back(tmp[i]);
                }
                current.pop_back(); // back track
            }
            return res;
        }
    };

Log in to reply
 

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