Fast DFS with pruning


  • 0
    C

    I just add three conditions to quick return from recursion.

    1. Is there enough elements?
    2. Is the sum of largest set of elements larger than target?
    3. Is current element already larger than target? since I sort the elements in ascending order.
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<int> res(k);
            vector< vector<int> > resList;
            combineRursion(1, 0, res, resList, n);
            return resList;
        }
        
        void combineRursion(int st, int k, vector<int>&res, vector< vector<int> >& resList, int target){
            if (target == 0 || k == res.size()){
                if (target == 0 && k == res.size()) resList.push_back(res);
                return;
            }
            if (9 - st + 1 < res.size() - k) return;
            if ((res.size() - k) * (9 - (res.size() - k) + 1 + 9) / 2 < target) return;
    
            for (int i = st; i <= 9; i++){
                if (i > target) break;
                res[k] = i;
                combineRursion(i + 1, k + 1, res, resList, target - i);
            }
        }

Log in to reply
 

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