算法学习——LeetCode力扣回溯篇1

在这里插入图片描述

77. 组合

77. 组合 - 力扣（LeetCode）

描述

任何顺序返回答案。

示例

示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示

1 <= n <= 20
1 <= k <= n

代码解析

回溯遍历法

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    //left是for的开始 ，right是for的结束。当size==k的时候递归结束
    void tarversal(int left , int right , int k)
    {
        if(path.size() == k)
        {
            result.push_back(path);
            return;
        }else
        {
            for(int i= left ; i <= right ; i++)
            {
                path.push_back(i);
                tarversal(i+1 ,right , k);
                path.pop_back();
            }
            return;
        }
       
    }
    vector<vector<int>> combine(int n, int k) {
        tarversal(1,n,k);
        return result;
    }
};

回溯剪枝法

剪枝是减少无意义循环的过程
在这里插入图片描述

当输入是n=4，k=4的时候，只有1234符合。我们遍历到2开始时，最多为234，234的长度为3满足长度为4的情况，是无意义的，要剪去。

for(int i= left ; i <= right - (k - path.size()) +1 ; i++) 为剪枝的判断

其中left为遍历的开始，right为遍历的结束。现在还需要找到k - path.size()个点
即 right - left => (k - path.size()) ，为剩下的点可以满足k的要求
=>left <= right - (k - path.size()) +1 ，其中+1为满足左边闭合。
例，k=3，n=4时，已经选取的为0个（path.size()=0），带入i <= right - ( k - path.size() ) +1 ， i <= 4 - （3-0）+1 ，为i<=2。
即当i最大为从2开始满足，为234 。大于2 剪枝

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void tarversal(int left , int right , int k)
    {
        if(path.size() == k)
        {
            result.push_back(path);
            return;
        }else
        {
           //i <= right - (k - path.size()) +1为剪枝的过程，避免无意义的循环
            for(int i= left ; i <= right - (k - path.size()) +1 ; i++)
            {
                path.push_back(i);
                tarversal(i+1 ,right , k);
                path.pop_back();
            }
            return;
        }
       
    }
    vector<vector<int>> combine(int n, int k) {
        tarversal(1,n,k);
        return result;
    }
};

216. 组合总和 III

216. 组合总和 III - 力扣（LeetCode）

描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次
返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示

2 <= k <= 9
1 <= n <= 60

代码解析

回溯法无减枝

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtraking(int k, int n , int sum ,int startidx)
    {
        if(path.size() == k && sum == n)
        {
            result.push_back(path);
            return;
        }else
        {
            for(int i= startidx ; i < 10 ; i++)
            {
                path.push_back(i);
                backtraking(k,n,sum+i,i+1);
                path.pop_back();
            }
            return;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtraking(k,n,0,1);
        return result;
    }
};

回溯剪枝

剪枝原理同 77题

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtraking(int k, int n , int sum ,int startidx)
    {
        if(sum > n) return;
        if(path.size() == k && sum == n)
        {
            result.push_back(path);
            return;
        }else
        {
            for(int i= startidx ; i < 10 - (k - path.size()) + 1 ; i++)
            {
                path.push_back(i);
                backtraking(k,n,sum+i,i+1);
                path.pop_back();
            }
            return;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtraking(k,n,0,1);
        return result;
    }
};

17. 电话号码的字母组合

17. 电话号码的字母组合 - 力扣（LeetCode）

描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

提示

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

代码解析

字符串

class Solution {
public:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    
    vector<string> result;
    //输入参：转换后的vector ， 从第几个按键开始循环 ， 已经走的路径
    void backtarcking(vector<int> &digits_i , int startidx , string path)
    { 	
    	//当路径的长度等于数组的长度，存入结果
        if(path.size() == digits_i.size() )
        {
            result.push_back(path);
            return;
        }
        else
        {	
        	//第一次循环，循环数字
            for(int i = startidx ; i < digits_i.size() ; i++)
            {
            	//找到输入数字对应的字母表
                string tmp = letterMap[digits_i[i]];
                vector<char> tmp_v(tmp.begin() , tmp.end()) ;
                //第二次循环，循环每一个数字的字母
                for(int j=0 ; j < tmp_v.size() ; j++)
                {
                	//递归回溯，开始循环的数字往后走一个，路径加上已经走的路径
                    backtarcking(digits_i, i+1 , path + tmp_v[j]);
                }
            }
            return;
        }
         return;
    }
    vector<string> letterCombinations(string digits) {
		//输入为空时直接返回
        if(digits.size()==0) return result;
		//字符串转换成vector
        vector<int> digits_i;
        for(auto i:digits) digits_i.push_back( i - '0' );
       
        string path;
        backtarcking(digits_i , 0 , path);

        return result;
    }
};

map表

class Solution {
public:
    vector<string> result;
    string worldPath;
    map<char,vector<string>> myMap;
    void map_init()
    {
        myMap.insert(pair<char,vector<string>>('2',{"a","b","c"})) ;
        myMap.insert(pair<char,vector<string>>('3',{"d","e","f"})) ;
        myMap.insert(pair<char,vector<string>>('4',{"g","h","i"})) ;
        myMap.insert(pair<char,vector<string>>('5',{"j","k","l"})) ;
        myMap.insert(pair<char,vector<string>>('6',{"m","n","o"})) ;
        myMap.insert(pair<char,vector<string>>('7',{"p","q","r","s"})) ;
        myMap.insert(pair<char,vector<string>>('8',{"t","u","v"})) ;
        myMap.insert(pair<char,vector<string>>('9',{"w","x","y","z"})) ;
        // for(auto it:myMap)
        //      cout<<it.first<<':'<<(it.second)[0]<<endl;
        // cout<<myMap['2'].size();
    }
    void dfs(string digits , int fir )
    {
        
        if( worldPath.size() == digits.size())
        {
            result.push_back(worldPath);
            return;
        }

        char num = digits[fir];
        for(int j=0 ; j< myMap[num].size() ;j++)
        {
            worldPath += myMap[num][j];
            dfs(digits,fir+1);
            worldPath.pop_back();
        }
        
        return;
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0) return result;
        map_init();
        dfs(digits,0);
        return result;
    }
};

39. 组合总和

39. 组合总和 - 力扣（LeetCode）

描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素互不相同
1 <= target <= 40

代码解析

暴力回溯（无剪枝，时间复杂度高）

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum;
    void backtracking(vector<int>& candidates, int target , int sum)
    {	
    	//检测目标大于时返回
        if(sum > target) return;
        if(sum == target)
        {
        	//排序后发现是新结果插入
            vector<int> tmp(path.begin(),path.end());
            sort(tmp.begin(),tmp.end());
            auto it = find(result.begin(),result.end(),tmp);
            if(it == result.end()) result.push_back(tmp);
            return;
        }
		//无任何限制回溯
        for(int i = 0 ; i < candidates.size() ;i++)
        {
            path.push_back(candidates[i]);
            backtracking(candidates,target,sum+candidates[i]);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
      
        backtracking(candidates,target,0);
        return result;
    }
};

回溯剪枝

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum;
    void backtracking(vector<int>& candidates, int target , int sum , int indnx)
    {
        if(sum > target) return;
        if(sum == target)
        {
            result.push_back(path);
            return;
        }
  		//剪枝，因为之前已经对输入进行排序，当发现加上i点的值大于目标后，后面的也都大于
        for(int i = indnx ; i < candidates.size() && sum+candidates[i] <= target ;i++)
        {
            path.push_back(candidates[i]);
            //递归的下一个指针和当前一样都是i，不是i+1 
            //因为一个数可以重复的使用，不能重复是i+1
            backtracking(candidates,target,sum+candidates[i] , i);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        //对输入进行排序，方便后面循环
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0,0);
        return result;
    }
};