第13章 回溯法
大约 8 分钟
第13章 回溯法
组合问题
剑指offerⅡ79：所有子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
写法一：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
if(nums.length==0){
return ans;
}
dfs(nums,0,new LinkedList<>(),ans);
System.out.println(ans.toString());
return ans;
}
private void dfs(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> ans){
if(index==nums.length){
ans.add(new LinkedList<>(subset));
return;
}
subset.add(nums[index]); //先选择下标为index的数
dfs(nums,index+1, subset, ans); //在选择index的情况下，确定index+1的选择情况
subset.removeLast(); //不选择下标为index的数
dfs(nums,index+1, subset, ans); //在不选择index的情况下，确定index+1的选择情况
}
}
剑指offerⅡ80：包含k个元素的组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> combination = new LinkedList<>();
dfs(1, n,k, ans, combination);
return ans;
}
private void dfs(int i, int n, int k, List<List<Integer>> ans, LinkedList<Integer> combination){
if(combination.size()==k){
ans.add(new LinkedList<>(combination));
return;
}
if(i <= n){
combination.add(i);
dfs(i+1, n,k, ans, combination);
combination.removeLast();
dfs(i+1, n,k, ans, combination);
}
}
}
剑指offerⅡ81：允许重复选择元素的组合
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> combination = new LinkedList<>();
Arrays.sort(candidates);
dfs(target, 0, candidates, combination, ans);
return ans;
}
private void dfs(int target, int i, int[] nums, LinkedList<Integer> combination, List<List<Integer>> ans) {
if (target == 0) {
ans.add(new LinkedList<>(combination));
return;
}
if (target > 0 && i < nums.length) {
// if(nums[i] > target){
// return;
// }
combination.add(nums[i]);//加入nums[i]
dfs(target - nums[i], i, nums, combination, ans);//判断是否可以继续加入nums[i]
combination.removeLast();//对于该层而言（这一点很重要，需要理解），删除一个nums[i]，相当于不将nums[i]加入其中
dfs(target, i + 1, nums, combination, ans);//那么要判断是否可以加入nums[i+1]
}
}
}
二刷遇到的问题：
- LinkedList才有removeLast方法
- 先排序，再剪枝，优化时间复杂度
上面的代码执行耗时:4 ms,击败了36.75% 的Java用户；内存消耗:39.1 MB,击败了5.70% 的Java用户。所以需要剪枝提速，又因为candidates里面都是正整数，所以可以在if(target > 0 && i < nums.length)中加入剪枝：if(candidates[i] > target){return;}
剑指offerⅡ82：包含重复元素的组合
给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> combination = new LinkedList<>();
Arrays.sort(candidates);
dfs(0, target, candidates, ans, combination);
return ans;
}
private void dfs(int i, int target, int[] nums, List<List<Integer>> ans, LinkedList<Integer> combination){
if(target==0){
ans.add(new LinkedList<>(combination));
return;
}
if(i<nums.length && target>0){
combination.add(nums[i]);
dfs(i+1,target-nums[i],nums,ans, combination);
combination.removeLast();
dfs(findNext(i, nums),target,nums, ans, combination);
}
}
private int findNext(int i, int[] nums){
int next = i;
while(next<nums.length && nums[i]==nums[next]){
next++;
}
return next;
}
}
LC17：电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
代码：
class Solution {
List<String> combinitions = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return combinitions;
}
Map<Character, String> num2letters = new HashMap<>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
dfs(0, digits, combinitions, new StringBuilder(), num2letters);
return combinitions;
}
private void dfs(int index, String digits, List<String> combinitions, StringBuilder combinition, Map<Character, String> num2letters) {
if (index == digits.length()) {
combinitions.add(combinition.toString());
return;
}
char digit = digits.charAt(index);
String letters2beSelected = num2letters.get(digit);
int lengthOfString = letters2beSelected.length();
for (int i = 0; i < lengthOfString; i++) {
combinition.append(letters2beSelected.charAt(i));
dfs(index + 1, digits, combinitions, combinition, num2letters);
combinition.deleteCharAt(index);
}
}
}
排列问题
剑指offerⅡ83：没有重复元素集合的全排列
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
经典解法：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> permutation = new LinkedList<>();
dfs(0,nums,ans,permutation);
return ans;
}
//确定位置i的数字
private void dfs(int i, int[] nums, List<List<Integer>> ans, LinkedList<Integer> permutation){
if(i==nums.length){
permutation.clear();
for(int num:nums){
permutation.add(num);
}
ans.add(new LinkedList<>(permutation));
return;
}
if(i<nums.length){
for (int j=i;j<nums.length;j++){//循环确定位置i的数字，遍历所有可能
swap(nums, i, j);
dfs(i+1,nums,ans,permutation);
swap(nums, i, j);
}
}
}
private void swap(int[] nums, int i, int j){
if(i!=j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
比较容易理解的解法：
剑指offerⅡ84：包含重复元素集合的全排列
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
LinkedList<Integer> permutation = new LinkedList<>();
dfs(nums, 0, ans, permutation);
return ans;
}
private void dfs(int[] nums, int i, List<List<Integer>> ans, LinkedList<Integer> permutation){
if(i==nums.length){
permutation = new LinkedList<>();
for(int num:nums){
permutation.add(num);
}
ans.add(permutation);
return;
}
Set<Integer> set = new HashSet<>();
for (int j=i;j<nums.length;j++){
if(!set.contains(nums[j])) {
set.add(nums[j]);//记录所有和nums[i]交换过的数字，如果再次遇到相同的数字，则跳过
swap(nums, i, j);
dfs(nums, i + 1, ans, permutation);
swap(nums, i, j);
}
}
}
private void swap(int[] nums, int i, int j){
if(i!=j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
用set来记录所有和nums[i]交换过的数字，如果发现有相同的数字已经被交换过了，则直接跳过该数字。
剑指offerⅡ85：生成匹配的括号
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 ：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
思路：
- 左括号或右括号的数目不能超过n个
- 任意步骤中，已经生成的右括号数目不能超过左括号数目
- 如果在上一步所有括号已经匹配，下一个括号只能是左括号
本书代码：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new LinkedList<>();
dfs(n, n, "", ans);
return ans;
}
private void dfs(int left, int right, String s, List<String> ans){
if(left == 0 && right == 0){
ans.add(s);
return;
}
if(left > 0){
dfs(left - 1, right, s + "(", ans);
}
if(left < right){
dfs(left, right - 1, s + ")", ans);
}
}
}
自己写的代码：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new LinkedList<>();
generate(0, 0, ans, new String(), n);
return ans;
}
private void generate(int left, int right, List<String> ans, String thesis, int n) {
if (left == n && right == n) {
ans.add(new String(thesis));
return;
}
if (left < n) {
generate(left + 1, right, ans, thesis + "(", n);
}
if (left > right) {
generate(left, right + 1, ans, thesis + ")", n);
}
}
}
在这个题目中，String作为包装类型，传入函数中被修改后，跳出函数中仍然是原来的值，这跟基本数据类型的表现一样，为什么会这样？可以从JVM的角度去解释。
剑指offerⅡ86：分割回文子字符串
给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
示例 2：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 3：
输入：s = "a"
输出：[["a"]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
书本的代码：
class Solution {
public String[][] partition(String s) {
List<String[]> res = new LinkedList<>();
dfs(res, new LinkedList<>(), 0, s);
return res.toArray(new String[res.size()][]);
}
private void dfs(List<String[]> res, LinkedList<String> substrings, int start, String s){
if(start == s.length()){
res.add(substrings.toArray(new String[substrings.size()]));
return;
}
for(int end=start;end<s.length();end++){
if(isPalindrome(start,end,s)){
substrings.add(s.substring(start, end+1));
dfs(res,substrings,end+1,s);
substrings.removeLast();
}
}
}
private boolean isPalindrome(int left, int right, String str){
while(left<right){
if(str.charAt(left++)!=str.charAt(right--)){
return false;
}
}
return true;
}
}
剑指offerⅡ87：恢复IP地址
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]
书上的代码：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new LinkedList<>();
dfs(s, 0, 0, "", "", result );
return result;
}
private void dfs(String s, int i, int segI, String seg, String ip, List<String> result){
if(i==s.length() && segI==3 && isValieSeg(seg)){
result.add(ip+seg);
return;
}
if(i<s.length()){
char ch = s.charAt(i);
if(isValieSeg(seg+ch)){
dfs(s, i+1, segI, seg+ch, ip, result);
}
if(seg.length()>0 && segI<3){
dfs(s, i+1, segI+1, ""+ch, ip+seg+".", result);
}
}
}
private boolean isValieSeg(String seg){
return Integer.valueOf(seg)<=255 && (seg.charAt(0)!='0'||seg.equals("0"));
}
}