此处为 Cpp 和 Java 回溯法模板；

    题目来源 LeetCode 39 组合总和；
    39 组合总和

    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

    题目难度： 中等； 关键词：回溯；

    1. class Solution {
    2. public:
    3.     vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    4.         sort(candidates.begin(),candidates.end());
    5.         vector<vector<int>> res;
    6.         vector<int> tmp;
    7.         dfs(candidates,res,tmp,target,0);
    8.         return res;
    9.     }
    10.     void dfs(const vector<int>& candidates, vector<vector<int>> &ans, vector<int> &tmp,int target,int index){
    11.         if(target<0) return; // 提前退出遍历，剪枝操作；
    12.         if(target==0){
    13.             ans.emplace_back(tmp); // 得到满足条件的结果，结束当前的集合更新；
    14.             return;
    15.         }
    16.         /* 这里利用循环之间的迭代更新来退出当前节点的选择 */
    17.         for(int start=index;start<candidates.size();++start){
    18.             if(target<0) break;
    19.             tmp.emplace_back(candidates[start]);
    20.             dfs(candidates,ans,tmp,target-candidates[start],start);
    21.             tmp.pop_back();
    23.         }
    24.     }
    25. };

    回溯是DFS的一个变体，很是类似于穷举法，但是通过在一个路径检索过程中会利用一些相关条件实现对检索路径的提前退出，有点像决策树的剪枝操作和训练模型时的早停法；