题解 | #和为S的连续正数序列#

回溯算法

class Solution {
public:
    void FindContinuousSequenceImpl(int sum, int curIdx, vector<int> &cur, int &curSum, vector<vector<int> > &result)
    {
        while (curSum > sum) {
            curSum -= cur[0];
            cur.erase(cur.begin());
        }

        if (curSum == sum) {
            result.push_back(cur);
            return;
        }    
        
        
        for (int i = curIdx; i <= sum - 1; i++) {
            cur.push_back(i);
            curSum += i;
            FindContinuousSequenceImpl(sum, i + 1, cur, curSum, result);
            if (cur.size() == 1) {
                // 走到这里时，正常情况cur应该有至少两个数，如果只有一个数了，说明前两个数相加已经大于sum，并且在第一步while循环中去掉第一个数了，
                // 之后再与新的数相加只会比这两个数和更大，不会再满足和为sum，已经遍历完毕
                return;
            } 
            curSum -= cur[0];
            cur.erase(cur.begin());
        }
    }
    
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > result;
        vector<int> cur;
        int curSum = 0;
        FindContinuousSequenceImpl(sum, 1, cur, curSum, result);
        
        return result;
    }
};