数据结构与算法：回溯-EW帮帮网

回溯

先给出一些leetcode算法题，以后遇见了相关题目再往上增加
主要参考代码随想录

2.1、组合问题

关于去重：两种写法的性能分析

需要注意的是：使用set去重的版本相对于used数组的版本效率都要低很多，大家在leetcode上提交，能明显发现。

原因在回溯算法：递增子序列 (opens new window)中也分析过，主要是因为程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）相对费时间，而且insert的时候其底层的符号表也要做相应的扩充，也是费时的。

而使用used数组在时间复杂度上几乎没有额外负担！

使用set去重，不仅时间复杂度高了，空间复杂度也高了，在本周小结！（回溯算法系列三） (opens new window)中分析过，组合，子集，排列问题的空间复杂度都是O(n)，但如果使用set去重，空间复杂度就变成了O(n^2)，因为每一层递归都有一个set集合，系统栈空间是n，每一个空间都有set集合。

那有同学可能疑惑用used数组也是占用O(n)的空间啊？

used数组可是全局变量，每层与每层之间公用一个used数组，所以空间复杂度是O(n + n)，最终空间复杂度还是O(n)。

1、77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 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>> res;
	vector<int> mid;
	void backt(int n,int k,int index){
		if(mid.size()==k){
			res.push_back(mid);
			return ;
		}
		for(int i = index;i<=n;i++){
			mid.push_back(i);
			backt(n,k,i+1);
			mid.pop_back();
		}
	}
	vector<vector<int>> combine(int n, int k) {
		backt(n,k,1);
		return res;
	}
};


// 使用function函数
// function<返回类型(参数类型1, 参数类型2, ...)> func;
class Solution {
public:
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> res;
		vector<int> mid;
		function<void(int)> backt = [&](int index){
			if(mid.size() == k){
				res.push_back(mid);
				return;
			}
			for(int i = index;i<=n;i++){
				mid.push_back(i);
				backt(i+1);
				mid.pop_back();
			}
		};
		backt(1);
		return res;
	}
};

时间复杂度: O(n * 2^n)
空间复杂度: O(n)

2、216. 组合总和 III

找出所有相加之和为 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>> combinationSum3(int k, int n) {
		vector<vector<int>> res;
		vector<int>  mid;
		function<void(int)> backt = [&](int index){
			if(mid.size() == k && n==0){
				res.push_back(mid);
				return;
			}
			if(n<0) return;
			for(int i =index;i<=9;i++ ){
				n = n-i;
                mid.push_back(i);
				backt(i+1);
				n = n+i;
                mid.pop_back();
			}
		};
		backt(1);
		return res;
	}
};

时间复杂度: O(n * 2^n)：每个数有两种可能选或者不选，这里不太理解
空间复杂度: O(n)

3、17. 电话号码的字母组合

给定一个仅包含数字 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:
	vector<string> letterCombinations(string digits) {
		unordered_map<int,string> mp;
		mp[2] = "abc";
		mp[3] = "def";
		mp[4] = "ghi";
		mp[5] = "jkl";
		mp[6] = "mno";
		mp[7] = "pqrs";
		mp[8] = "tuv";
		mp[9] = "wxyz";
		vector<string> res;
		string mid;
        if(digits.size()==0) return {};
		function<void(int)> backt = [&](int index){
			if(mid.size() == digits.size()){
				res.push_back(mid);
				return;
			}
			for(auto a:mp[digits[index]-'0']){
				mid.push_back(a);
				backt(index+1);
				mid.pop_back();
			}
		};
        backt(0);
		return res;
	}
};

4、39. 组合总和

给你一个 无重复元素 的整数数组 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>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> res;
		vector<int> mid;
		function<void(int)> backt = [&](int index){
			if(target == 0){
				res.push_back(mid);
				return ;
			}
			if(target<0) return;
			for(int i = index;i<candidates.size();i++){
				target = target - candidates[i];
				mid.push_back(candidates[i]);
				backt(i);
				mid.pop_back();
				target = target + candidates[i];
			}
		};
        backt(0);
		return res;
	}
};

5、40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

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

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

/*
	前几道题目都是常规的回溯，这个题目要求去重；
	去重方法：给原始数据排完序的前提下：每一层的重复的去掉
	所以有两种方法，：
	第一种：每一个backt中创建一个set去重
	第二种：直接通过挨个的下标去重：但是有一点需要注意
	i是从index+1开始与前一个比较去重
	if(i>index)这个一定不能忘记
	if(i>index&&candidates[i] == candidates[i-1] ) continue;
	这句话是每一层第一个下标肯定是index，又为了和前面有个比较，所以需要i>index:说明前面已经处理这个元素了不用再处理了
*/
class Solution {
public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> res;
		vector<int> mid;
		int len = candidates.size();
		function<void(int)> backt = [&](int index){
			if(target == 0){
				res.push_back(mid);
			}
			if(target<0) return;
			// unordered_set<int> st;
			for(int i = index;i<len;i++){
				// if(st.count(candidates[i])) continue;
                //这句话是每一层第一个下标肯定是index，又为了和前面有个比较，所以需要i>index:说明前面已经处理这个元素了不用再处理了
                if( i>index&&candidates[i] == candidates[i-1] ) continue;
				// st.insert(candidates[i]);
				target-=candidates[i];
				mid.push_back(candidates[i]);
				backt(i+1);
				mid.pop_back();
				target+=candidates[i];
			}
		};
        sort(candidates.begin(),candidates.end());
		backt(0);
		return res;
	}
};

2.2、子集问题

1、78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

/*
	经典子集问题，模板题
*/
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> mid;
        function<void(int)> backt = [&](int index) {
            res.push_back(mid);
            for (int i = index; i < nums.size(); i++) {
                mid.push_back(nums[i]);
                backt(i + 1);
                mid.pop_back();
            }
        };
        backt(0);
        return res;
    }
};

2、90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的

子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

/*
	去重子集问题：
	与去重组合问题一个思路：先排序，每一层的重复元素跳过即可：最后的结果就会去重复：
	两个方法：
	第一个：每一层set去重
	第二个：每一层index+1开始向前判断是否相等
*/

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

        vector<vector<int>> res;
        vector<int> mid;

        sort(nums.begin(), nums.end());

        function<void(int)> backt = [&](int index) {
            res.push_back(mid);
            for (int i = index; i < nums.size(); i++) {
                if (i > index && nums[i] == nums[i - 1])
                    continue;
                mid.push_back(nums[i]);
                backt(i + 1);
                mid.pop_back();
            }
        };
        backt(0);
        return res;
    }
};

3、491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

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

提示：

1 <= nums.length <= 15
-100 <= nums[i] <= 100

/*
	思路：还是去重问题：
	主要是这个无法排序，还需要去重
	这时候两个相同的元素就不是挨着的了，所以只能用那个set去解决
	所以：无法排序的使用set去重即可
*/
class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> mid;
        function<void(int)> backt = [&](int index) {
            if(mid.size()>=2){
                res.push_back(mid);
            }
            unordered_set<int> st;
            for (int i = index; i < nums.size(); i++) {
                if(st.count(nums[i])) continue;
                st.insert(nums[i]);
                if(mid.empty()){
                    mid.push_back(nums[i]);
                    backt(i + 1);
                    mid.pop_back();
                }
                else if(!mid.empty() && mid.back()<=nums[i]){
                    mid.push_back(nums[i]);
                    backt(i + 1);
                    mid.pop_back();
                }
            }
        };
        backt(0);
        return res;
    }
};

2.3、排列问题

1、46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

/*
	思路：唯一的区别就是不需要坐标了，每一层都从头到尾来一遍
	加上过了的直接跳过
*/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> mid;
        vector<bool> visited(nums.size(), false);
        function<void()> backt = [&]() {
            if (mid.size() == nums.size()) {
                res.push_back(mid);
                return;
            }
            for (int i = 0; i < nums.size(); i++) {
                if (visited[i])
                    continue;
                mid.push_back(nums[i]);
                visited[i] = true;
                backt();
                mid.pop_back();
                visited[i] = false;
            }
        };
        backt();
        return res;
    }
};

时间复杂度: O(n*n!)：因为有跳过的所以就是阶乘
空间复杂度: O(n)

2、47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

/*
	排列问题降重：只要能排序同样是两个思路：
	但是set更好理解
	使用相邻坐标判断的时候注意122的问题：需要加上visited的约束
*/

class Solution {
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>>res;
		vector<int> mid;
		vector<bool> visited(nums.size(),false);
		function<void()> backt=[&](){
			if(mid.size()==nums.size()){
				res.push_back(mid);
				return;
			}	
			// unordered_set<int> st;
			for(int i = 0;i<nums.size();i++){
				if(visited[i]) continue;
                if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;

				// st.insert(nums[i]);
				mid.push_back(nums[i]);
				visited[i] = true;
				backt();
				mid.pop_back();
				visited[i] = false;
			}
		};
		sort(nums.begin(),nums.end());
		backt();
		return res;
	}
};

时间复杂度: 最差情况所有元素都是唯一的。复杂度和全排列1都是 O(n! * n) 对于 n 个元素一共有 n! 中排列方案。而对于每一个答案，我们需要 O(n) 去复制最终放到 result 数组
空间复杂度: O(n) 回溯树的深度取决于我们有多少个元素

2.3、切割问题

1、131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是

回文串

。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

/*
	思路：切割注意左右就行
	i为右，维护一个左下标就可以了
	比如aab
	a      aa     aab
	a ab   b
	b
	新的左下标为 i+1
	那么截至条件就是左边下标为s.size() = 3	
	
	这种题目记住维护左右下标，如何找个例子去模拟一下再去写代码
*/

class Solution {
public:
    bool istar(string s, int left, int right) {
        while (left <= right) {
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> mid;
        function<void(int)> backt = [&](int left) {
            if (left == s.size()) {
                res.push_back(mid);
            }
            for (int i = left; i < s.size(); i++) {
                if (istar(s, left, i)) {
                    mid.push_back(s.substr(left, i - left + 1));
                    backt(i + 1);
                    mid.pop_back();
                }
            }
        };
        backt(0);
        return res;
    }
};

2、93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

1 <= s.length <= 20
s 仅由数字组成

/**
	模拟一下，细节较多但是还是左右的下标去截取
*/
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        string mid;
        function<void(int,int)> backt = [&](int left,int cnt) {
            if (cnt==4&&left == s.size()) {
                mid.pop_back();
                res.push_back(mid);
                return;
            }
            if(cnt>4) return;
            for (int right = left; right < s.size(); right++) {
                string cur;
                string precur;
                cur = s.substr(left, right - left + 1);
                if(cur.size()>3) continue;
                int cur_num = stoi(cur);
                if ((cur.size()>1&&cur[0] == '0') || cur_num > 255)
                    continue;
                precur = mid;
                mid += cur;
                mid.push_back('.');
                backt(right + 1,cnt+1);
                mid = precur;
            }
        };
        backt(0,0);
        return res;
    }
};

数据结构与算法：回溯

回溯

2.1、组合问题

1、77. 组合

2、216. 组合总和 III

3、17. 电话号码的字母组合

4、39. 组合总和

5、40. 组合总和 II

2.2、子集问题

1、78. 子集

2、90. 子集 II

3、491. 非递减子序列

2.3、排列问题

1、46. 全排列

2、47. 全排列 II

2.3、切割问题

1、131. 分割回文串

2、93. 复原 IP 地址

网站公告

今日签到

热门文章

最新发布