本文共 5436 字，大约阅读时间需要 18 分钟。
这篇文章是关于我今天所做的关于回溯算法的题（出自力扣），参考了力扣上几位大牛的算法，在此表示感谢！
1. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3]] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5]]class Solution { public List > combinationSum(int[] candidates, int target) { List > list =new ArrayList<>(); Arrays.sort(candidates); findAllCombine(list,candidates,target,0,new ArrayList ()); //System.out.println(list); return list; } private static void findAllCombine(List > list, int[] candidates, int target, int start, ArrayList al) { //System.out.println("target:"+target); if(target<0) { return; } if(target==0) { list.add(new ArrayList (al)); return; } for(int i=start;i
2. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。 示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]class Solution { public List > combinationSum2(int[] candidates, int target) { List > list=new ArrayList<>(); Arrays.sort(candidates); findAllOnly(list,new ArrayList (),candidates,target,0); //System.out.println(list); return list; } private static void findAllOnly(List > list, ArrayList al, int[] candidates, int target, int start) { if(target<0) { return ; } if(target==0) { if(!list.contains(al)) { list.add(new ArrayList<>(al)); } return; } for(int i=start;i
3. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明： 所有数字都是正整数。 解集不能包含重复的组合。 示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2:输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]class Solution { public List > combinationSum3(int k, int n) { List > ls=new ArrayList<>(); int [] candidates=new int[9]; for(int i=0;i<9;i++) { candidates[i]=i+1; } //System.out.println(Arrays.toString(candidates)); //找到九个数中等于n的排列组合 findEqualN(candidates,ls,new ArrayList (),0,n,k); //System.out.println(ls); return ls; } private static void findEqualN(int[] candidates, List > ls, ArrayList al, int start, int target, int k) { if(target<0) { return; } if(target==0) { if(al.size()==k) { ls.add(new ArrayList<>(al)); } return ; } for(int i=start;i
4. 组合总和 IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例:
nums = [1, 2, 3]
target = 4所有可能的组合为：
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶： 如果给定的数组中含有负数会怎么样？ 问题会产生什么变化？ 我们需要在题目中添加什么限制来允许负数的出现？ 注：这是力扣上那位大牛的代码，我没有改class Solution { public int combinationSum4(int[] nums, int target) { //dfs会超时 //使用dp数组，dp[i]代表组合数为i时使用nums中的数能组成的组合数的个数 //别怪我写的这么完整 //dp[i]=dp[i-nums[0]]+dp[i-nums[1]]+dp[i=nums[2]]+... //举个例子比如nums=[1,3,4],target=7; //dp[7]=dp[6]+dp[4]+dp[3] //其实就是说7的组合数可以由三部分组成，1和dp[6]，3和dp[4],4和dp[3]; int[]dp=new int[target+1]; //是为了算上自己的情况，比如dp[1]可以由dp【0】和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]; }} 5. 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]class Solution { public List > permute(int[] nums) { List >arraylist=new ArrayList<>(); return recursion(arraylist, nums, 0, nums.length-1); } //核心 public static List > recursion(List > al,int[]nums,int begin,int end){ List al2=new ArrayList<>(); if(begin==end){ for(int i=0;i<=end;i++){ al2.add(nums[i]); } al.add(al2); return al; }else{ for(int j=begin;j<=end;j++){ exch(nums,begin,j); recursion(al,nums, begin+1, end); exch(nums,begin,j); } return al; } } //交换 private static void exch(int[] nums, int i, int j) { int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; }}
6. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ [‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’], [‘A’,‘D’,‘E’,‘E’]] 给定 word = “ABCCED”, 返回 true. 给定 word = “SEE”, 返回 true. 给定 word = “ABCB”, 返回 false.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 =0 && row =0 && col 7. 最大单词长度乘积
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。示例 1:
输入: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
输出: 16 解释: 这两个单词为 “abcw”, “xtfn”。 示例 2:输入: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出: 4 解释: 这两个单词为 “ab”, “cd”。 示例 3:输入: [“a”,“aa”,“aaa”,“aaaa”]
输出: 0 解释: 不存在这样的两个单词。class Solution { public int maxProduct(String[] words) { //先将所有的单词用32的整数进行表示 int [] val=new int[words.length]; for(int i=0;i 转载地址：http://udhq.baihongyu.com/