本文共 7834 字，大约阅读时间需要 26 分钟。
给定一个无重复元素的数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。数组中的数字可以无限制重复被选取。所有数字（包括 target）都是正整数。解集不能包含重复的组合。
candidates = [2,3,6,7], target = 7 输出：[[7], [2,2,3]]candidates = [2,3,5], target = 8 输出：[[2,2,2,2], [2,3,3], [3,5]]使用回溯算法，尝试所有可能的组合，排除重复的情况。通过排序和递归的方式，确保每个组合的元素不重复，并且总和等于目标。
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution { public List > combinationSum(int[] candidates, int target) { List > result = new ArrayList<>(); Arrays.sort(candidates); findAllCombination(result, candidates, target, 0, new ArrayList<>()); return result; } private static void findAllCombination(List > result, int[] candidates, int target, int start, List path) { if (target < 0) { return; } if (target == 0) { if (!result.contains(path)) { result.add(new ArrayList<>(path)); } return; } for (int i = start; i < candidates.length; i++) { int num = candidates[i]; if (num > target) { continue; } if (path.contains(num)) { continue; } path.add(num); findAllCombination(result, candidates, target - num, i, path); path.remove(); if (target - num == 0) { return; } } } }
给定一个数组 candidates 和一个目标数 target，找出所有可以使数字和为 target 的组合。每个数字在每个组合中只能使用一次。
candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 输出：[[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]candidates = [2, 5, 2, 1, 2], target = 5 输出：[[1, 2, 2], [5]]使用回溯算法，确保每个数字在组合中只使用一次。通过排序和递归的方式，生成所有满足条件的组合。
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution { public List > combinationSum2(int[] candidates, int target) { List > result = new ArrayList<>(); Arrays.sort(candidates); findAllOnly(result, new ArrayList<>(), candidates, target, 0); return result; } private static void findAllOnly(List > result, List path, int[] candidates, int target, int start) { if (target < 0) { return; } if (target == 0) { if (!result.contains(path)) { result.add(new ArrayList<>(path)); } return; } for (int i = start; i < candidates.length; i++) { int num = candidates[i]; if (num > target) { continue; } if (path.contains(num)) { continue; } path.add(num); findAllOnly(result, path, candidates, target - num, i); path.remove(); } } }
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有1-9的正整数，并且每种组合中不存在重复的数字。
k = 3, n = 7 输出：[[1, 2, 4]]k = 3, n = 9 输出：[[1, 2, 6], [1, 3, 5], [2, 3, 4]]生成所有可能的1-9数组，然后使用回溯算法找出所有满足条件的组合。确保组合中数字不重复，且总和等于目标。
import java.util.ArrayList;import java.util.List;public class Solution { public List > combinationSum3(int k, int n) { List > result = new ArrayList<>(); int[] candidates = new int[9]; for (int i = 0; i < 9; i++) { candidates[i] = i + 1; } findEqualN(candidates, result, new ArrayList<>(), 0, n, k); return result; } private static void findEqualN(int[] candidates, List > result, List path, int start, int target, int k) { if (target < 0) { return; } if (target == 0) { if (path.size() == k) { result.add(new ArrayList<>(path)); } return; } for (int i = start; i < candidates.length; i++) { int num = candidates[i]; if (num > target) { continue; } if (path.contains(num)) { continue; } path.add(num); findEqualN(candidates, result, path, i, target - num, k); path.remove(); } } }
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。顺序不同的序列被视作不同的组合。
输入：nums = [1, 2, 3], target = 4 输出：7种组合。
使用动态规划的方法，创建一个dp数组，dp[i]表示组合数为i时使用nums中的数能组成的组合数的个数。通过遍历数组中的每个数，更新dp数组，统计满足条件的组合数。
public class Solution { public int combinationSum4(int[] nums, int target) { int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int num : nums) { if (i >= num) { dp[i] += dp[i - num]; } } } return dp[target]; }} 给定一个没有重复数字的序列，返回其所有可能的全排列。
输入：[1, 2, 3] 输出：6种排列。
使用递归的方法，生成所有可能的排列。通过交换元素位置的方式，确保每个排列都是唯一的。
import java.util.ArrayList;import java.util.List;public class Solution { public List > permute(int[] nums) { List > result = new ArrayList<>(); return recursion(result, nums, 0, nums.length - 1); } public static List > recursion(List > result, int[] nums, int begin, int end) { List path = new ArrayList<>(); if (begin == end) { for (int i = 0; i <= end; i++) { path.add(nums[i]); } result.add(new ArrayList<>(path)); return result; } else { for (int j = begin; j <= end; j++) { swap(nums, begin, j); recursion(result, nums, begin + 1, end); swap(nums, begin, j); } } return result; } private static void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，相邻单元格是水平或垂直的。
网格：
['A', 'B', 'C', 'E']['S', 'F', 'C', 'S']['A', 'D', 'E', 'E']
单词："ABCCED"，返回true。
使用深度优先搜索（DFS），记录每个访问过的单元格，避免重复访问。检查单词是否能按顺序找到。
public class Solution { public boolean exist(char[][] board, String word) { char[] chs = word.toCharArray(); int rows = board.length; int cols = board[0].length; boolean[][] visited = new boolean[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (isvalid(i, j, chs, 0, visited)) { return true; } } } return false; } private boolean isvalid(int row, int col, char[] chs, int index, boolean[][] visited) { if (row < 0 || row >= visited.length || col < 0 || col >= visited[0].length) { return false; } if (visited[row][col]) { return false; } if (index >= chs.length) { return true; } if (board[row][col] == chs[index]) { visited[row][col] = true; if (isvalid(row, col, chs, index + 1, visited)) { return true; } visited[row][col] = false; } return false; }} 给定一个字符串数组，找到两个单词的长度乘积的最大值，前提是它们没有公共字母。如果没有这样的两个单词，返回0。
["abcw", "baz", "foo", "bar", "xtfn", "abcdef"] 输出：16["a", "ab", "abc", "d", "cd", "bcd", "abcd"] 输出：4["a", "aa", "aaa", "aaaa"] 输出：0首先统计每个单词的字母频率，然后找出两个没有公共字母的单词，计算它们的长度乘积的最大值。
public class Solution { public int maxProduct(String[] words) { int[] letterCount = new int[26]; for (String word : words) { for (char c : word.toCharArray()) { letterCount[c - 'a']++; } } int maxProduct = 0; for (int i = 0; i < words.length; i++) { int[] cnt1 = letterCount; for (int j = i + 1; j < words.length; j++) { int[] cnt2 = letterCount; if (checkOverlap(words[i], cnt1, words[j], cnt2)) { int product = words[i].length() * words[j].length(); if (product > maxProduct) { maxProduct = product; } } } } return maxProduct; } private boolean checkOverlap(String word1, int[] cnt1, String word2, int[] cnt2) { for (char c : word1.toCharArray()) { if (cnt2[c - 'a'] > 0) { return true; } } return false; }} 通过以上内容，可以看到回溯算法在解决各种组合问题中的应用。每个问题都有其独特的挑战，但通过系统的分析和优化，可以找到有效的解决方案。
转载地址：http://udhq.baihongyu.com/