回溯算法

一、理论基础

1.回溯算法主要用于解决以下问题：组合、排列、切割、子集、排列、棋盘。

2.回溯算法分析模板如下：

 void backtracking(参数) {
     if (终止条件) {
         存放结果;
         return;
     }
 ?
     for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
         处理节点;
         backtracking(路径，选择列表); // 递归
         回溯，撤销处理结果
     }
 }

3.组合问题

 class Solution {
 public:
     vector<vector<int>> result; // 存放符合条件结果的集合
     vector<int> path; // 用来存放符合条件结果
     void backtracking(int n, int k, int startIndex) {
         if (path.size() == k) {
             result.push_back(path);
             return;
         }
         for (int i = startIndex; i <= n; i++) {  
 //剪枝优化：在集合n中至多可开始的位置：n-(k-path.size())+1
             path.push_back(i); // 处理节点 
             backtracking(n, k, i + 1); // 递归
             path.pop_back(); // 回溯，撤销处理的节点
         }
     }
     vector<vector<int>> combine(int n, int k) {
         result.clear(); // 可以不写
         path.clear();   // 可以不写
         backtracking(n, k, 1);
         return result;
     }
 };

4.组合总和问题

 class Solution {
 public:
     vector<vector<int>> result; // 存放符合条件结果的集合
     vector<int> path; // 用来存放符合条件结果
     void backtracking(vector<int>& num, int target,int sums,int startIndex) {
         if(sums>target) return;
         if (sums==target) {
             result.push_back(path);
             return;
         }
         for (int i = startIndex; i < num.size(); i++) {  
 //剪枝优化：在集合n中至多可开始的位置：n-(k-path.size())+1(如果规定了组合个数，且是递增数组)
             path.push_back(num[i]); // 处理节点 
             sums +=num[i];
             backtracking(num, target, sums,i ); // 递归
             sums-=num[i];
             path.pop_back(); // 回溯，撤销处理的节点
         }
     }
     vector<vector<int>> combine(vector<int>& num, int target) {
         result.clear(); // 可以不写
         path.clear();   // 可以不写
         backtracking(num, target,0,1);
         return result;
     }
 };

TRANSLATE with

Bing Webmaster Portal

• 中文（简体）
• 中文（繁体）
• 丹麦语
• 乌克兰语
• 乌尔都语
• 亚美尼亚语
• 俄语
• 保加利亚语
• 克罗地亚语
• 冰岛语
• 加泰罗尼亚语
• 匈牙利语
• 卡纳达语
• 印地语
• 印尼语
• 古吉拉特语
• 哈萨克语
• 土耳其语
• 威尔士语
• 孟加拉语
• 尼泊尔语
• 布尔语(南非荷兰语)
• 希伯来语
• 希腊语
• 库尔德语
• 德语
• 意大利语
• 拉脱维亚语
• 挪威语
• 捷克语
• 斯洛伐克语
• 斯洛文尼亚语
• 旁遮普语
• 日语
• 普什图语
• 毛利语
• 法语
• 波兰语
• 波斯语
• 泰卢固语
• 泰米尔语
• 泰语
• 海地克里奥尔语
• 爱沙尼亚语
• 瑞典语
• 立陶宛语
• 缅甸语
• 罗马尼亚语
• 老挝语
• 芬兰语
• 英语
• 荷兰语
• 萨摩亚语
• 葡萄牙语
• 西班牙语
• 越南语
• 阿塞拜疆语
• 阿姆哈拉语
• 阿尔巴尼亚语
• 阿拉伯语
• 韩语
• 马尔加什语
• 马拉地语
• 马拉雅拉姆语
• 马来语
• 马耳他语
• 高棉语