LeetCode刷题笔记之回溯算法（一）

一、回溯算法的基础知识

1. 回溯算法本质上是一种穷举算法，回溯算法一定伴随着递归，回溯算法就是遍历树枝。
2. 站在回溯树的一个节点上，你只需要思考 3 个问题：
   • 路径：也就是已经做出的选择；
   • 选择列表：也就是你当前可以做的选择；
   • 结束条件：也就是到达决策树底层，无法再做选择的条件。
3. 回溯算法的模板：

List result = new ArrayList();
public void backtrack(路径, 选择列表){if(满足结束条件){result.add(路径);return;}for(选择 : 选择列表){ //层序遍历做选择;backtrack(路径, 选择列表); //递归遍历撤销选择;}
}

4. 需要使用回溯算法解决的问题：
   • 组合问题：N个数里面按一定规则找出k个数的集合；
   • 切割问题：一个字符串按一定规则有几种切割方式；
   • 子集问题：一个N个数的集合里有多少符合条件的子集；
   • 排列问题：N个数按一定规则全排列，有几种排列方式；
   • 棋盘问题：N皇后，解数独等等

二、组合问题

组合是无序的，即{1，2}与{2，1}是同一个组合。

1. 77【组合】

• 题目： 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。
• 代码：

class Solution {public List<Integer> path = new LinkedList<>();public List<List<Integer>> ansList = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {//首先确定回溯法构造的树的根下面第一层是n个节点，即for循环的判别条件是<=n//终止条件是每条路径包含k个元素//需要进行剪枝，当剩余元素无法满足path.size()==k，是推出循环backtrack(n,k,1);return ansList;}public void backtrack(int n, int k, int index){if(path.size() == k){ansList.add(new ArrayList<>(path));//不能直接将path加入anList，因为path是引用类型return;}for (int i = index; i <= n-(k-path.size())+1; i++) {path.add(i);backtrack(n,k,i+1);path.removeLast();}}
}

2. 216【组合总和III】

• 题目： 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件。返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
  • 只使用数字1到9；
  • 每个数字 最多使用一次。
• 代码：

class Solution {public List<Integer> path = new LinkedList<>();public List<List<Integer>> ansList = new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {//终止条件是path中包含k个数//构造的树的根下面的第一层包含[1,9]backtrack(k,n,1);return ansList;}public void backtrack(int k,int n,int index){if(path.size()==k){int sums = 0;for (int i = 0; i < k; i++) {sums += path.get(i);}if(sums == n){ansList.add(new ArrayList<>(path));}return;}for (int i = index; i <= 9-(k-path.size())+1 ; i++) {path.add(i);backtrack(k,n,i+1);path.removeLast();}}
}

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

• 题目： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
• 代码：

class Solution {public List<String> ansList = new ArrayList<>();public StringBuilder path = new StringBuilder();HashMap<Character,String> map = new HashMap<>();public List<String> letterCombinations(String digits) {//首先使用map存储每个数字对应的字符串//这里的循环需要进行次数为每个输入数字所表示的字符串的长度//递归次数为输入数字字符串的长度if(digits.length() == 0) return new ArrayList<>();map.put('2',"abc");map.put('3',"def");map.put('4',"ghi");map.put('5',"jkl");map.put('6',"mno");map.put('7',"pqrs");map.put('8',"tuv");map.put('9',"wxyz");backtrack(digits,digits.length(),0);return ansList;}public void backtrack(String digits,int len,int index){//终止条件是path里有len个字符if(path.length() == len){ansList.add(path.toString());return;}String s = map.get(digits.charAt(index));for (int i = 0; i < s.length(); i++) {path.append(s.charAt(i));backtrack(digits,len,index+1);path.deleteCharAt(path.length()-1);}}
}

4. 39【组合总和】

• 题目： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
  candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
  对于给定的输入，保证和为 target 的不同组合数少于 150 个。
• 代码：

class Solution {public List<List<Integer>> ansList = new ArrayList<>();public List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {//本题的特点是不限制元素出现次数，组合的数量//因此，终止条件就为sum>=target//另外为了提高效率，在循环时进行剪枝，需要对数组进行排序Arrays.sort(candidates);backtrack(candidates,target,0,0);return ansList;}public void backtrack(int[] candidates, int target, int sum,int index){if(sum == target){ansList.add(new ArrayList<>(path));return;}for (int i = index; i<candidates.length && sum+candidates[i]<=target; i++) {sum += candidates[i];path.add(candidates[i]);backtrack(candidates,target,sum,i);sum -= path.get(path.size()-1);path.removeLast();}}}

5. 40【组合总和II】

• 题目： 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  candidates 中的每个数字在每个组合中只能使用 一次 。
  注意：解集不能包含重复的组合。
• 代码：

class Solution {public List<List<Integer>> ansList = new ArrayList<>();public List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {//本题的与上一题的区别是每个元素只能出现一次//因此在排序之后，循环时需要跳过相同的元素//并不是所有遇到相同元素的情况就要跳过//只有两个节点属于同一递归深度时才跳过Arrays.sort(candidates);backtrack(candidates,target,0,0);return ansList;}public void backtrack(int[] candidates,int target,int sum,int index){if(sum == target){ansList.add(new ArrayList<>(path));return;}for(int i=index;i<candidates.length && sum+candidates[i]<=target;i++){if(i>index && candidates[i] == candidates[i-1]) continue;sum += candidates[i];path.add(candidates[i]);backtrack(candidates,target,sum,i+1);sum -= path.get(path.size()-1);path.removeLast();}}
}

三、切割问题

6. 131【分割回文串】

• 题目： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
  回文串 是正着读和反着读都一样的字符串。
• 代码：

class Solution {List<List<String>> ansList = new ArrayList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {//第i层选取从第i个元素为起始点进行分割，//因此，需要记录每次进行分割的起始点//递归时要将起始点+1//每次分割都要判断当前部分是否满足回文串的要求//终止条件是起始点到最后一个元素backtrack(s,0);return ansList;}public void backtrack(String s,int index){if(index >= s.length()){ansList.add(new ArrayList<>(path));return;}for(int i=index;i<s.length();i++){String subStr = s.substring(index,i+1);if(!isPalindrome(subStr)){continue;}else{path.add(subStr);}backtrack(s,i+1);path.removeLast();}}public boolean isPalindrome(String str){for (int i = 0, j=str.length()-1; i < j; i++,j--) {if(str.charAt(i) != str.charAt(j)){return false;}}return true;}
}

7. 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 中的任何数字。你可以按 任何 顺序返回答案。
• 代码：

class Solution {public List<String> ansList = new ArrayList<>();public List<String> restoreIpAddresses(String s) {//和上一题相似，需要对字符串进行分割//终止条件是出现了3个.，即分割3次backtrack(s,0,0);return ansList;}public void backtrack(String s, int index, int pointNum){if(pointNum == 3){if(isValid(s.substring(index))){ansList.add(s);}return;}for (int i = index; i < s.length(); i++) {String str = s.substring(index,i+1);if(!isValid(str) || i+1==s.length()){break;}else{str = s.substring(0,i+1)+"."+s.substring(i+1);pointNum++;backtrack(str,i+2,pointNum);pointNum--;str = s.substring(0,i+1)+s.substring(i+2);}}}public boolean isValid(String subStr){if(subStr.length()>3 || subStr==""){return false;}if(subStr.length()>1 && subStr.charAt(0)=='0'){return false;}int i = Integer.parseInt(subStr);if(i>255){return false;}return true;}
}

四、子集问题

8. 78【子集】

• 题目： 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。
• 代码：

class Solution {public List<List<Integer>> ansList = new ArrayList<>();public List<Integer> subSet = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {//寻找所有子集，意味着需要记录所有节点的值ansList.add(new ArrayList<>(subSet));backtrack(nums,0);return ansList;}public void backtrack(int[] nums,int index){if(index >= nums.length){return;}for (int i = index; i < nums.length; i++) {subSet.add(nums[i]);ansList.add(new ArrayList<>(subSet));backtrack(nums,i+1);subSet.removeLast();}}
}

9. 90【子集II】

• 题目： 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
  解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
• 代码：

class Solution {public List<List<Integer>> ansList = new ArrayList<>();public List<Integer> subSet = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {//本题与上一题的区别是有重复元素//因此需要对数组进行排序Arrays.sort(nums);ansList.add(new ArrayList<>(subSet));backtrack(nums,0);return ansList;}public void backtrack(int[] nums,int index){if(index == nums.length){return;}for (int i = index; i < nums.length; i++) {if(i!=index && nums[i] == nums[i-1]){continue;}subSet.add(nums[i]);ansList.add(new ArrayList<>(subSet));backtrack(nums,i+1);subSet.removeLast();}}
}

10. 491【非递减子序列】

• 题目： 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
  数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
• 代码：

class Solution {List<List<Integer>> ansList = new ArrayList<>();List<Integer> subSet = new LinkedList<>();public List<List<Integer>> findSubsequences(int[] nums) {//注意题中要求子序列至少有2个元素//数组中有重复元素，所以在同一递归层要判断改元素之前是否使用过//可以使用map和数组，因为这里数组的值在[-100,100]//所以这里使用数组记录某一递归层是否使用过某一元素backtrack(nums,0);return ansList;}public void backtrack(int[] nums, int index){if(subSet.size() > 1) {ansList.add(new ArrayList<>(subSet));}int[] used = new int[201];for(int i=index;i<nums.length;i++){if(used[nums[i]+100] == 1) continue;if(!subSet.isEmpty() && subSet.get(subSet.size()-1)>nums[i]){continue;}subSet.add(nums[i]);used[nums[i]+100] = 1;backtrack(nums,i+1);subSet.removeLast();}}
}