leetcode刷题

回溯其实和递归是相辅相成的，有递归就一定有回溯。只是有些题目用到的到，有些题目用不到。

回溯其实也是暴力解法，只是有些题目只能暴力解决。

回溯问题其实就是类似于n叉树的遍历。

回溯的大致模板：

backing(){
    if 终止条件
        return；
    递归条件；
    回溯操作；
    return；
}

组合问题：

void backing(vector<vector<int>> &result, vector<int> & zuhe, int n, int k){
        
        if(zuhe.size() == k){
            result.push_back(zuhe);
            return ;
        }
            
        for(int i = 1; i <= n; i++){    
            if(zuhe.size() == 0){                      //
                zuhe.push_back(i);
                backing(result, zuhe, n, k);
                zuhe.pop_back();
            }
            else{
                if(i > zuhe.back()){
                    zuhe.push_back(i);
                    backing(result, zuhe, n, k);
                    zuhe.pop_back();
            }
            }
        }      
        return ;
    }
vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> zuhe;
        backing(result, zuhe, n, k);
        return result;
    }

虽然是暴力解法，但还是可以通过剪枝操作降低时间复杂度。比如该问题，如果后续剩余可以加入的元素比现有的少了，就不需要再遍历了。