目录
22. 括号生成
39. 组合总和
46. 全排列
77. 组合
79. 单次搜索
回溯全集
22. 括号生成
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]
思路：用left和right分别记录'('和')'的剩余数量
class Solution {
List<String> result = new ArrayList<>();
public List<String> generateParenthesis(int n) {
if (n == 0) {
return result;
}
backTrack("", n, n);
return result;
}
//left 和 right 分别表示剩余'('和')'的数量
public void backTrack(String current, int left, int right) {
if (left == 0 && right == 0) {
result.add(current);
return;
}
if (left == right) {
//如果相等，则只能放'('
backTrack(current + '(', left-1, right);
} else {
//如果不相等，则'('和')'都能放
if (left > 0) {
backTrack(current + '(', left-1, right);
}
backTrack(current + ')', left, right-1);
}
}
}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 输出: []
思路：回溯+剪枝
class Solution {
int target_ = 0;
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates.length == 0) {
return result;
}
target_ = target;
Arrays.sort(candidates); //排序
backTrack(candidates, 0, 0, new ArrayList<>());
return result;
}
public void backTrack(int[] candidates, int start, int summ, List<Integer> current) {
if (summ == target_) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i< candidates.length; i++) {
//剪枝
if (candidates[i] + summ > target_) {
break;
}
current.add(candidates[i]);
//由于可以重复，因此这里是从i开始，不是从i+1开始
backTrack(candidates, i, summ + candidates[i], current);
current.remove(current.size()-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]]
思路：最基础的回溯
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return result;
}
backTrack(nums, 0);
return result;
}
public void backTrack(int[] nums, int start) {
if (start == nums.length - 1) {
List<Integer> temp = new ArrayList<>();
for (int num : nums) {
temp.add(num);
}
result.add(temp);
return;
}
for (int i = start; i< nums.length; i++) {
swap(nums, i, start);
backTrack(nums, start+1);
swap(nums, i, start);
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}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]]
思路：关键是每次从i+1开始
class Solution {
List<List<Integer>> result = new ArrayList<>();
int k_ = 0;
public List<List<Integer>> combine(int n, int k) {
if (n == 0 || k == 0) {
return result;
}
k_ = k;
backTrack(n, new ArrayList<>(), 1);
return result;
}
public void backTrack(int n, List<Integer> current, int start) {
if (current.size() == k_) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i <= n; i++) {
current.add(i);
//每次从i+1开始,保证不重复
backTrack(n, current, i+1);
current.remove(current.size() - 1);
}
}
}79. 单次搜索
给定一个
m x n二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" 输出：true示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" 输出：false
思路：. - 力扣（LeetCode）
class Solution {
public boolean exist(char[][] board, String word) {
if (board.length == 0 || board[0].length == 0 || word.length() == 0) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
//每次以第[i,j]为开始，进行搜索
if (backTrack(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
public boolean backTrack(char[][] board, String word, int start, int i, int j) {
//如果超过边界，返回false
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ) {
return false;
}
//如果不相等，范围false
if (word.charAt(start) != board[i][j]) {
return false;
}
//相等，且为最后一位，范围true
if (start == word.length()-1) {
return true;
}
char temp = board[i][j];
//为了防止回退，每次把当前设置成一个其他字符，这样就不会产生回退
board[i][j] = '&';
boolean result = backTrack(board, word, start+1, i+1, j) ||
backTrack(board, word, start+1, i, j+1) ||
backTrack(board, word, start+1, i-1, j) ||
backTrack(board, word, start+1, i, j-1);
board[i][j] = temp;
return result;
}
}
