试探法

回溯法又称为试探法，指的是在寻找解的过程中，遍历所有可能，如果是解，那么保存，否则不保存，无论是否保存都退回到上一步。

递归

回溯算法递归实现

递归的函数中，出点一般有两个：

1. 解是所求的那么需要将解保存，并return
2. 解不是所求的或者不满足条件，那么可以在for中直接pass，或者添加一个出点直接return。

递归实现中，需要的容器有两个：

1. 最终结果容器
2. 临时容器
   该容器随着函数的进栈出栈，不停地变化。进栈该容器元素增加，出栈该容器元素减少。

需要额外的指示变量用来记录临时容器状态或者说是目前得到解的状态，该变量的作用：用来判断temp是否满足解的要求，在额外限制条件中是否应该跳过即将要处理的一个节点。

所以框架一般为

void backtracking(vector<vector<int>> &result,vector<int> &temp,int k)
{
    //当递归到了最低层，需要返回的两个出点
    //第一个出点(可以没有)：该出点表示当前容器的结果不满足要求。直接返回
    if()
    {
        return;
    }
    //第二个出点(一般都有)：该出点表示当前结果满足要求，所以将目前临时容器的副本存入最终结果容器
    if()
    {
        result.push_back(vector<int>(temp));
    }

    //递归没有到最底层，还能继续深入。
    //如果在for中添加额外的限制添加，那么第一出点就可以不要。    
    //这里还有一个隐含的条件是:依次遍历
    for()
    {
        //添加额外的限制条件
        if()
        {
            //使用continue跳过
            continue;
        }

        //将当前处理的节点添加入temp
        temp.push_back(...);
        //这里不一定是k-1。
        backtracking(result,temp,k-1);

        //只要执行到这一句，意味着递归到达最底层，开始返回。
        //需要需要将底层push的元素pop出
        //这里不处理结果是否满足，因为在底层出点的时候已经判断过了。
        //这里的作用就是为了去遍历其他可能。
        temp.pop_back();
    }
}

递归实现的框架一般是这样的。

例题

1. leetcode 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
意思是：给定一个n用来构建一个包含从1到n的集合，返回这个集合的子集，子集需要满足元素个数是k。

分析

1. 最终结果容器和临时容器，都是很好判断的
2. 两个出点
   把一个元素添加进临时容器，就将k--,那么当k=0时就表示临时容器中有两个元素。此时保存临时容器的副本。
   方k<0的时候？发生了什么？应该不会发生。
3. 要求只是子集的元素个数是k

#include <vector>
#include <iostream>
using namespace std;

void combinations(vector<vector<int>> &result,vector<int> &temp,int total,int tmpStart,int k)
{
    //这里不需要第一个出点，因为不会有k<0的情况啊
    //第二个出点(一般都有)：该出点表示当前结果满足要求，所以将目前临时容器的副本存入最终结果容器
    if(k==0)
    {
        result.push_back(vector<int>(temp));
    }

    //递归没有到最底层，还能继续深入。
    //如果在for中添加额外的限制添加，那么第一出点就可以不要。    
    //这里还有一个隐含的条件是:依次遍历
    for(int start = tmpStart;start<=total;start++)
    {
        //这里没有额外限制
        //将当前处理的节点添加入temp
        temp.push_back(start);
        //这里不一定是k-1。
        combinations(result,temp,total,tmpStart+1,k-1);

        //只要执行到这一句，意味着递归到达最底层，开始返回。
        //需要需要将底层push的元素pop出
        //这里不处理结果是否满足，因为在底层出点的时候已经判断过了。
        //这里的作用就是为了去遍历其他可能。
        temp.pop_back();
    }
}

void combinationsPacking(int n,int k)
{
    //需要判断一下n,k
    vector<vector<int>> result;
    vector<int> temp;
    backtracking(result,temp,n,1,k);
    cout<<"end;"<<endl;
    for(int i=0;i<result.size();i++)
    {
        cout<<"\n[";
        for(int j =0;j<result[i].size();j++)
        {
            cout<<result[i][j];
            if((j+1)<result[i].size())
            {
                cout<<",";
            }
        }
        cout<<"]\n";        
    }
}

int main()
{
    combinationsPacking(7,2);
}

上面的代码，有一点
临时容器pop(),而k不变，因为本层的k不需要变化，也没有发生过变化。

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
意思是：返回所有的子集，且原来的集合中可能含有重复的元素

分析

1. 容器还是那两个
2. 出点这次并不需要判断需要满足什么条件了，第二出点直接保存
3. 而判断重复元素应该是在for中
   我们需要将集合排序。
   然后在处理一个元素的时候，如果当前元素与集合的上一个元素相同那么就跳过。
   因为如果两个相同的两个元素，前面的那个结果已经等于后面的了。

#include <vector>
#include <iostream>
using namespace std;

void subsets(vector<vector<int>> &result,vector<int> &temp,vector<int> &resource,int tmpStart)
{
    //这里不需要第一个出点，因为不会有k<0的情况啊
    //第二个出点,也没有。最终的出点就是递归到底层，自动返回
    result.push_back(vector<int>(temp));
    
   // cout<<"result: "<<result.size()<<" tmpStart: "<<tmpStart<<endl;
    //递归没有到最底层，还能继续深入。
    //如果在for中添加额外的限制添加，那么第一出点就可以不要。    
    //这里还有一个隐含的条件是:依次遍历
    for(int start = tmpStart;start<resource.size();start++)
    {   
        //额外限制
        if(resource[start]==resource[start-1] && start > 0)
        {
            continue;
        }
        //将当前处理的节点添加入temp
        temp.push_back(resource[start]);
        //这里不一定是k-1。
        subsets(result,temp,resource,start+1);        
       
        //无论结果是否是需要的，都需要pop，去遍历其他的可能
        temp.pop_back();
    }
}

void subsetsPacking(vector<int> &resource)
{
    //需要判断一下n,k
    vector<vector<int>> result;
    vector<int> temp;
    subsets(result,temp,resource,0);
    for(int i=0;i<result.size();i++)
    {
        cout<<"\n[";
        for(int j =0;j<result[i].size();j++)
        {
            cout<<result[i][j];
            if((j+1)<result[i].size())
            {
                cout<<",";
            }
        }
        cout<<"]\n";
    }
}

int main()
{
    vector<int> i{1,1,2,3};
    subsetsPacking(i);
}

3. permutations

Given a collection of distinct numbers, return all possible permutations.
就是给定一个数组，输出所有可能的排序

这个题相对简单：

1. 两个容器
2. 没有指示变量
   因为需要遍历所有的元素，而不是从后道歉依次遍历。
3. 出点
   临时容器中的元素和输入容器的元素相同时，将临时容器的副本保存进最终容器中
4. 额外限制
   将要处理的元素，不能在临时容器中，如果已经在临时容器中，那么提过。
   换句话说，这个题，不能有重复元素。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void permutations(vector<vector<int>> &result,vector<int> &temp,vector<int> &resource,int tmpStart)
{
    //第二个出点:当临时容器中的元素数量达到resource.size()时
    if(temp.size()==resource.size())
    {
        result.push_back(vector<int>(temp));
    }

    for(int start = 0;start<resource.size();start++)
    {
        //额外限制条件应该是，该元素没有被添加过。
        if(find(temp.begin(),temp.end(),resource[start]) != temp.end())
        {
            continue;
        }

        temp.push_back(resource[start]);
        permutations(result,temp,resource,start+1);
        
        temp.pop_back();
    }
}

void permutationsPacking(vector<int> &resource)
{
    //需要判断一下n,k
    vector<vector<int>> result;
    vector<int> temp;
    permutations(result,temp,resource,0);
    for(int i=0;i<result.size();i++)
    {
        cout<<"\n[";
        for(int j =0;j<result[i].size();j++)
        {
            cout<<result[i][j];
            if((j+1)<result[i].size())
            {
                cout<<",";
            }
        }
        cout<<"]\n";
    }
}

int main()
{
    vector<int> i{1,2,3,4,5,6};
    permutationsPacking(i);
}

4. permutations2 *******

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
存在重复元素，排序。

相比上一个题，需要变化的就是额外条件，同时，也学要一个额外的指示变量
跳过的条件应该是：

1. 要处理的元素如果已经处理过了，那么跳过
2. 要处理的元素，如果在输入结合中和上一个元素相同，那么跳过
   所以需要先给序列排序，如果和上一个相同，那么这个元素的排序结果和上一个是相同的，而且还没有被处理过。应该跳过。
   原因在于：当前节点B，其上一个节点为A
   那么，如果B的分支已经处理完毕，并返回，那么B被标记为未处理。
   那么当，B节点的分支开始处理时，经过A节点，A节点的状态应该就是没有被处理过。
   （意思是：1.当以A为根节点处理时，memo[A]=true,这时，表示A被添加了，但是不代表A遍历完了。
   当以A为根节点处理完毕以后，memo[A]=false,那么当以B为根节点在此遍历的时候，发现B和A值，一样，而且B已经已经处理完毕了）
   不好讲，脑中过一遍栈，就能明白。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void permutations(vector<vector<int>> &result,vector<int> &temp,vector<int> &resource,vector<bool> &memo)
{
    //第二个出点:当临时容器中的元素数量达到resource.size()时
    if(temp.size() == resource.size())
    {
        result.push_back(vector<int>(temp));
        return;
    }

    for(int start = 0; start<resource.size(); start++)
    {
        cout<<"start: "<<start<<" memo : "<<memo[start]<<" value : "<<resource[start]<<" temp size : "<<temp.size()<<endl;
        //额外限制条件应该是，该元素没有被添加过。
        if(memo[start] == true
            || ( start > 0 && resource[start] == resource[start-1] && memo[start-1] == false))
        {
            cout<<"continue"<<endl;
            continue;
        }
        memo[start] = true;
        temp.push_back(resource[start]);
        permutations(result,temp,resource,memo);
        memo[start]=false;
        temp.pop_back();
    }
}

void permutationsPacking(vector<int> &resource)
{
    //需要先排序
    vector<vector<int>> result;
    vector<int> temp;
    vector<bool> memo(resource.size(),false);
    permutations(result,temp,resource,memo);
    for(int i=0;i<result.size();i++)
    {
        cout<<"\n[";
        for(int j =0;j<result[i].size();j++)
        {
            cout<<result[i][j];
            if((j+1)<result[i].size())
            {
                cout<<",";
            }
        }
        cout<<"]\n";
    }
}

int main()
{
    vector<int> i{1,1,3};
    permutationsPacking(i);
}

·