递归专题

回溯算法的写法：

画出递归树，找到状态变量（回溯函数的参数）

根据题意确立结束条件

找准选择列表

判断是否需要剪枝（去掉重复的集合，即去掉递归树上的某些分支）

做出选择，递归调用，进入下一层

撤销选择

77. 组合

//给出n，k返回可能的组合
vector<vector<int>> res;
vector<int> temp;

void dfs(int cur, int n, int k)
{
    // 如果[cur, n]中元素的个数加上temo中元素的个数少于k，无法构成需要的组合
    if (temp.size() + (n - cur + 1) < k)
    {
        return;
    }
    // 如果temp的size == k，说明找到了组合，插入res
    if (temp.size() == k)
    {
        res.push_back(temp);
        return;
    }
    // 小于k的话继续往里添加元素
    if (temp.size() < k)
    {
        // 考虑选择当前位置
        temp.push_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
}


vector<vector<int>> combine(int n, int k) {
    dfs(1, n, k);
    return res;
}

39. 组合总和

// 因为是数据可重复选择的情况，所以在回溯中，可选择跳过和不跳过当前数值，这样就会包括某一个值重复选择的情况，在不跳过当前值的选择中，需要确定当前数值没有超过所需值
vector<vector<int>> res;
vector<int> temp;

void dfs(int cur, int n, vector<int>& candidates, int remain)
{        
    if(cur == n)
    {
        return;
    }
    if(remain == 0)
    {
        res.push_back(temp);
        return;
    }
    // 不选择当前位置，直接跳过
    dfs(cur + 1, n, candidates, remain);
    // 选择当前数，不跳过，不跳过的话需要判断当前数是否还能选择
    if(candidates[cur] <= remain)
    {
        temp.push_back(candidates[cur]);
        remain -= candidates[cur]; 
        dfs(cur, n, candidates, remain);
        temp.pop_back();
    }
       
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
{
    int n = candidates.size();
    dfs(0, n,candidates, target);
    return res;
}

401. 二进制手表

vector<string> res;
unordered_map<int, int> hashdata = {{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};
void backtrack(int num,int start,pair<int,int>& time){
    // 结束条件
    if(num == 0)
    {
        if(time.first > 11 || time.second > 59)
        {
            return;
        }
        string temp_hour = to_string(time.first);
        string temp_minute = to_string(time.second);
        if(temp_minute.size() == 1)
        {
            temp_minute.insert(0, "0");
        }
        res.push_back(temp_hour + ":" + temp_minute);
        return;
    }
    for(int i = start; i < 10; i++)
    {
        if(time.first > 11 || time.second > 59)
        {
            continue;
        }
        // 在本层中创建一个变量store用来存储当前的time值，回退时使用
        pair<int, int> store = time;
        if(i < 4)
        {
            time.first += hashdata[i];
        }
        else
        {
            time.second += hashdata[i];
        
        }
        backtrack(num - 1, i + 1, time);
        // 在同层回退时把前面存好的store再赋给time，时time恢复到原状态
        time = store;
        
    }
}

vector<string> readBinaryWatch(int num) {
    pair<int, int> time(0, 0);
    backtrack(num, 0, time);
    return res;
}

40. 组合总数2

// 去重复结果组合使用pair计数，将给的数组里的相同数值的数放在一起去递归处理
vector<int> temp;
vector<vector<int>> res;
vector<pair<int, int>> freq;

void dfs(int pos, int rest)
{
    if(rest == 0)
    {
        res.push_back(temp);
        return;
    }
    if(pos == freq.size() || rest < freq[pos].first)
    {
        return;
    }
    

    dfs(pos+1, rest);
	// most用来判断处理相同数值的数时，进行几次递归，例如有五个2，但是target是7，那么只进行对2这个数值只进行三次递归
    int most = min(rest / freq[pos].first, freq[pos].second);    
    for(int a = 1; a <= most; a++)
    {
        temp.push_back(freq[pos].first);
        dfs(pos+1, rest - a * freq[pos].first);
    }
    for(int b = 1; b <= most; b++)
    {
        temp.pop_back();
    }
  
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    // vector<pair<int, int>> freq;
    sort(candidates.begin(), candidates.end());
    for(int num : candidates)
    {
        if(freq.empty() || num != freq.back().first)
        {
            // 用push_back的话需要make_pair，用emplace_back则不需要
            // freq.push_back(make_pair(num, 1));
            freq.emplace_back(num, 1);
        }
        else
        {
            ++freq.back().second;
        }
    }
    dfs(0, target);
    return res;
}

216. 组合总数3

vector<int> temp;
vector<vector<int>> res;

void dfs(int cur, int remain, int k)
{
    if(remain == 0 && temp.size() == k)
    {
        res.push_back(temp);
        return;
    }
    if(cur > remain || temp.size() == k || cur > 9)
    {
        return;
    }
    temp.push_back(cur);
    dfs(cur+1, remain-cur, k);
    temp.pop_back();
    dfs(cur+1, remain, k);
}

vector<vector<int>> combinationSum3(int k, int n) {
    dfs(1, n, k);
    return res;
}

22. 括号生成

回溯函数参数：要生成的括号对数n，存结果的vector rets，单个结果的string ret，当前左括号数open，当前右括号数close

用ret.size() == 2 * n判断是否将ret添加到结果rets

用open < n判断是否继续添加左括号

用close < open判断当前是否能添加右括号

46. 全排列

什么情况适合使用回溯法：

通过探索所有可能的候选解来找出所有解

终止条件为：

cur == len

回溯体结构为：

从已构造长度开始往后，逐个与当前位置进行数据交换

for(int i = cur; i < len; i++)
{
	swap(output[cur], output[i]);
    backtrack(ret, output, cur+1, len);
    swap(output[cur], output[i]); //回溯里一定要记得的撤销操作
}

78. 子集

没啥说的，最基础的回溯….