回溯算法习题集
易错点
- 遇到元素重复的题，一定要记住对数组排序
Arrays.sort(nums)- 遇到求和target的题目，要在判断条件中加入if(trackSum > target) {return;}
- 当遇到多个集合的问题时，只需要递归加嵌套循环即可，电话号码以及N皇后均是此类问题。
- 括号生成问题关键：[1,i]中左括号数量 >= 右括号数量
1. leetcode-77：组合
题目：给定两个整数 n 和 k，返回范围[1, n]中所有可能的k个数的组合。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
public List> combine(int n, int k) {
backtrack(n,1,k);
return res;
}
void backtrack(int n, int start, int k) {
if(track.size() == k) {
res.add(new LinkedList<>(track));
return;
}
for(int i=start; i<=n-(k-track.size())+1; i++) {
track.add(i);
backtrack(n,i+1,k);
track.removeLast();
}
}
}
2. leetcode-216：组合III
题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：(1)、只使用数字1到9 (2)、每个数字最多使用一次
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
int trackSum = 0;
public List> combinationSum3(int k, int n) {
backtrack(k,1,n);
return res;
}
void backtrack(int k, int start, int n) {
if(trackSum > n) {
return;
}
if(track.size() == k && trackSum == n) {
res.add(new LinkedList<>(track));
return;
}
for(int i=start; i<=9-(k-track.size())+1; i++) {
trackSum += i;
track.add(i);
backtrack(k,i+1,n);
track.removeLast();
trackSum -= i;
}
}
}
3. leetcode-39：组合之和
题目：给你一个无重复元素的整数数组 candidates 和一个目标整数target ，找出 candidates中可以使数字和为目标数target的所有不同组合，并以列表形式返回。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
int trackSum = 0;
public List> combinationSum(int[] candidates, int target) {
backtrack(candidates,target,0);
return res;
}
void backtrack(int[] candidates, int target, int start) {
if(trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
if(trackSum > target) {
return;
}
for(int i=start; i 4. leetcode-40：组合II
题目：给定一个候选人编号的集合candidates和一个目标数 target ，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
int trackSum = 0;
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backtrack(candidates,target,0);
return res;
}
void backtrack(int[] candidates, int target, int start) {
if(trackSum == target) {
res.add(new LinkedList<>(track));
return;
}
if(trackSum > target) {
return;
}
for(int i=start; i start && candidates[i] == candidates[i-1]) {
continue;
}
trackSum += candidates[i];
track.add(candidates[i]);
backtrack(candidates,target,i+1);
trackSum -= candidates[i];
track.removeLast();
}
}
}
5. leetcode-78：子集
题目：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
public List> subsets(int[] nums) {
backtrack(nums,0);
return res;
}
void backtrack(int[] nums, int start) {
res.add(new LinkedList<>(track));
for(int i=start; i 6. leetcode-90：子集II
题目：给你一个整数数组nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集不能包含重复的子集
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
public List> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(nums,0);
return res;
}
void backtrack(int[] nums, int start) {
res.add(new LinkedList<>(track));
for(int i=start; i start && nums[i] == nums[i-1]) {
continue;
}
track.add(nums[i]);
backtrack(nums,i+1);
track.removeLast();
}
}
}
7. leetcode-46：全排列
题目：给定一个不含重复数字的数组nums，返回其所有可能的全排列。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
boolean[] used;
public List> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if(track.size() == nums.length) {
res.add(new LinkedList<>(track));
return;
}
for(int i=0; i 8. leetcode-47：全排列II
题目：给定一个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
boolean[] used;
public List> permuteUnique(int[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if(track.size() == nums.length) {
res.add(new LinkedList<>(track));
return;
}
for(int i=0; i 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
used[i] = true;
track.add(nums[i]);
backtrack(nums);
track.removeLast();
used[i] = false;
}
}
}
9. leetcode-17：电话号码的字母组合
题目：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。
class Solution {
List res = new LinkedList<>();
String[] mapping = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List letterCombinations(String digits) {
if(digits.isEmpty()) {
return res;
}
backtrack(digits,0,new StringBuilder());
return res;
}
void backtrack(String digits, int start, StringBuilder sb) {
if(sb.length() == digits.length()) {
res.add(sb.toString());
return;
}
for(int i=start; i 另一种思路：
class Solution {
List res = new LinkedList<>();//结果集
String[] mapping = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
StringBuilder sb = new StringBuilder();//路径集
public List letterCombinations(String digits) {
if(digits.isEmpty()) {
return res;
}
backtrack(digits,0);
return res;
}
void backtrack(String digits, int row) {
if(sb.length() == digits.length()) {
res.add(sb.toString());
return;
}
//第一行循环，第二行循环...
String str = mapping[digits.charAt(row) - '0'];
for(int i=0; i 10. leetcode-491：递增子序列
题目：给你一个整数数组nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素 。你可以按任意顺序返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
class Solution {
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
public List> findSubsequences(int[] nums) {
backtack(nums,0);
return res;
}
void backtack(int[] nums, int start) {
Set used = new HashSet<>();
if(track.size() > 1) {
res.add(new LinkedList<>(track));
}
for(int i=start; i 11. leetcode-51：N皇后
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
class Solution {
//相当于两个集合组合在一起
List> res = new LinkedList<>();
LinkedList track = new LinkedList<>();
public List> solveNQueens(int n) {
char[][] board = new char[n][n];
for(int i=0; i(track));
return;
}
for(int i=0; i=0 && j>=0; i--,j--) {
if(board[i][j] == 'Q') return false;
}
for(int i=row-1,j=col+1; i>=0 && j 12. leetcode-37：解数独
题目：编写一个程序，通过填充空格来解决数独问题。
class Solution {
public void solveSudoku(char[][] board) {
backtrack(board);
}
boolean backtrack(char[][] board) {
for(int i=0; i<9; i++) { //遍历行
for(int j=0; j<9; j++) { //遍历列
if(board[i][j] != '.') {
continue;
}
for(char k='1'; k<='9'; k++) {
if(!isValid(board,i,j,k)) { //(i,j)位置放k是否合适
continue;
}
board[i][j] = k;
if(backtrack(board)) return true; //一个位置找到一个合适的数字立马返回
board[i][j] = '.';
}
return false; //9个数都试完了，没有true就返回false
}
}
return true; //所有的都试完了，没有返回false,就返回true
}
boolean isValid(char[][] board, int row, int col, char n) {
for(int i=0; i<9; i++) {
if(board[row][i] == n) return false;
}
for(int i=0; i<9; i++) {
if(board[i][col] == n) return false;
}
int rowStart = (row/3)*3;
int colStart = (col/3)*3;
for(int i=rowStart; i13. leetcode-22：括号生成
题目：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
class Solution {
List res = new LinkedList<>();
StringBuilder track = new StringBuilder();
public List generateParenthesis(int n) {
backtrack(n,n);
return res;
}
void backtrack(int left, int right) { //left为左括号剩余数量，right为右括号剩余数量，
if(left < 0 ||right < 0) {
return;
}
if(left > right) { //[0,i]中左括号的数量肯定大于等于右括号
return;
}
if(left == 0 && right ==0) {
res.add(track.toString());
return;
}
track.append('(');
backtrack(left-1,right);
track.deleteCharAt(track.length()-1);
track.append(')');
backtrack(left,right-1);
track.deleteCharAt(track.length()-1);
}
}
声明：转载自力扣网