• 数据结构与算法------回溯算法

    77. 组合

    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

    你可以按 任何顺序 返回答案。

    思路：首先组合问题，就是结果中不能出现重复，然后我们要用一个startIndex来移动每一个集合里的数字，比如第一层1，2，3.。。。n,第二层2，3，4.。。n,此时startIndex=1,然后一次移动到n去不同的值。startIndex就是用来去重的。

    示例 1：

    输入：n = 4, k = 2
    输出：
    [
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]
    示例 2：

    输入：n = 1, k = 1
    输出：[[1]]

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     LinkedList path=new LinkedList<>();
    4.     public List> combine(int n, int k) {
    5.  
    6.         backTrack(n,k,1);
    7.  
    8.         return res;
    9.     }
    10.  
    11.     public void backTrack(int n,int k,int startIndex){
    12.         if(path.size()==k){
    13.             res.add(new ArrayList<>(path));
    14.             return;
    15.         }
    16.  
    17.         for(int i=startIndex;i<=n-(k-path.size())+1;i++){//n-(k-path.size())+1剪枝
    18.             path.add(i);
    19.             backTrack(n,k,i+1);
    20.             path.removeLast();
    21.         }
    22.  
    23.     }
    24. }

    39. 组合总和

    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

    candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

    对于给定的输入，保证和为 target 的不同组合数少于 150 个。

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     LinkedList path=new LinkedList<>();
    4.     public List> combinationSum(int[] candidates, int target) {
    5.         backTrack(candidates,0,target);
    6.  
    7.         return res;
    8.     }
    9.  
    10.     public void backTrack(int[] candidates,int startIndex,int target){
    11.         if(target==0){
    12.             res.add(new ArrayList<>(path));
    13.             return;
    14.         }else if(target<0){
    15.             return;
    16.         }
    17.  
    18.         for(int i=startIndex;i
    19.             path.add(candidates[i]);
    20.             backTrack(candidates,i,target-candidates[i]);
    21.             path.removeLast();
    22.         }
    23.     }
    24. }

    示例 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
    输出: []

    40. 组合总和 II

    给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的每个数字在每个组合中只能使用 一次 。

    注意：解集不能包含重复的组合。 

    示例 1:

    输入: candidates = [10,1,2,7,6,1,5], target = 8,
    输出:
    [
    [1,1,6],
    [1,2,5],
    [1,7],
    [2,6]
    ]
    示例 2:

    输入: candidates = [2,5,2,1,2], target = 5,
    输出:
    [
    [1,2,2],
    [5]
    ]

    1. class Solution {
    2.     List> res = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> combinationSum2(int[] candidates, int target) {
    6.         Arrays.sort(candidates);
    7.         backTrack(candidates,0,target);
    8.         return res;
    9.     }
    10.  
    11.     public void backTrack(int[] candidates,int startIndex,int target){
    12.         if(target==0){
    13.             res.add(new ArrayList<>(path));
    14.             return;
    15.         }else if(target<0){
    16.             return;
    17.         }
    18.         for(int i=startIndex;i
    19.             if(startIndex1]){
    20.               continue;
    21.             }
    22.             path.add(candidates[i]);
    23.             backTrack(candidates,i+1,target-candidates[i]);
    24.             path.removeLast();
    25.             
    26.         }
    27.     }
    28. }

    216.组合总和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]]

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     LinkedList path=new LinkedList<>();
    4.     public List> combinationSum3(int k, int n) {
    5.         backTrack(k,n,1);
    6.  
    7.         return res;
    8.     }
    9.  
    10.     public void backTrack(int k,int n,int startIndex){
    11.         if(path.size()==k && n==0){//收集到k个元素并且集合中元素和为n
    12.             res.add(new ArrayList<>(path));
    13.             return;
    14.         }
    15.  
    16.         for(int i=startIndex;i<=9;i++){
    17.             path.add(i);
    18.             backTrack(k,n-i,i+1);
    19.             path.removeLast();
    20.         }
    21.     }
    22. }

    17. 电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    示例 1：

    输入：digits = "23"
    输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
    示例 2：

    输入：digits = ""
    输出：[]
    示例 3：

    输入：digits = "2"
    输出：["a","b","c"]

    1. class Solution {
    2.  
    3.     //设置全局列表存储最后的结果
    4.     List res= new ArrayList<>();
    5.     StringBuilder sb=new StringBuilder();
    6.     public List letterCombinations(String digits) {
    7.         if(digits.length()==0) return res;
    8.  
    9.         String[] s={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    10.  
    11.         backTrack(digits,s,0);
    12.  
    13.         return res;
    14.     }
    15.  
    16.     public void backTrack(String digits,String[] s,int num){
    17.         if(num==digits.length()){
    18.             res.add(sb.toString());
    19.             return;
    20.         }
    21.         String str=s[digits.charAt(num)-'0'];
    22.         for(int i=0;i
    23.             sb.append(str.charAt(i));
    24.             backTrack(digits,s,num+1);
    25.             sb.deleteCharAt(sb.length()-1);
    26.             
    27.         }
    28.     }
    29. }

    组合总和，组合总和II,组合总和III，电话号码组合总结：组合问题注意这几点：1.确定是组合问题，也就是说元素中不能有重复的 2.是否有startIndex,如果每次取的数都是一个集合取出的那么要startIndext;如果多个集合取数据那么不需要startIndex，比如电话号码数，第一个abc，第二个取def 3.能否重复选取元素，如果能那么就是i，不能就是i+1；4.看所给数组(原数据)是否含重复的，如果含重复需要去重，去重一定要先排序！如果不含重复的则不需要去重。

    131. 分割回文串

    给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

    回文串 是正着读和反着读都一样的字符串。

    示例 1：

    输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

    示例 2：

    输入：s = "a"
输出：[["a"]]
    1. class Solution {
    2.     List> res = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> partition(String s) {
    6.         backTrack(s,0);
    7.  
    8.         return res;
    9.     }
    10.  
    11.     public void backTrack(String s,int startIndex){
    12.         if(startIndex>=s.length()){
    13.             res.add(new ArrayList<>(path));
    14.             return;
    15.         }
    16.  
    17.         for(int i=startIndex;i
    18.             if(isNum(s,startIndex,i)){
    19.                 String str=s.substring(startIndex,i+1);
    20.                 path.add(str);
    21.             }else{
    22.                 continue;
    23.             }
    24.             backTrack(s,i+1);
    25.             path.removeLast();
    26.         }
    27.     }
    28.  
    29.     public boolean isNum(String s,int start,int end){
    30.        
    31.         while(start
    32.             if(s.charAt(start)!=s.charAt(end)){
    33.                return false;
    34.             }
    35.             start++;
    36.             end--;
    37.         }
    38.         return true;
    39.     }
    40. }

    93.复原IP地址

    给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。

    示例 1：

    • 输入：s = "25525511135"
    • 输出：["255.255.11.135","255.255.111.35"]

    示例 2：

    • 输入：s = "0000"
    • 输出：["0.0.0.0"]

    示例 3：

    • 输入：s = "1111"
    • 输出：["1.1.1.1"]

    示例 4：

    • 输入：s = "010010"
    • 输出：["0.10.0.10","0.100.1.0"]

    示例 5：

    • 输入：s = "101023"
    • 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

    提示：

    • 0 <= s.length <= 3000
    • s 仅由数字组成
    1. class Solution {
    2.     List res= new ArrayList<>();
    3.     
    4.     public List restoreIpAddresses(String s) {
    5.         backTrack(s,0,0);
    6.  
    7.         return res;
    8.     }
    9.     
    10.     public void backTrack(String s,int startIndex,int pointNum){
    11.             if(pointNum==3){
    12.                 if(isVaild(s,startIndex,s.length()-1)){
    13.                     res.add(s);   
    14.                 }
    15.                     return;
    16.             }
    17.           
    18.         for(int i=startIndex;i
    19.             if(isVaild(s,startIndex,i)){
    20.                 s=s.substring(0,i+1)+"."+s.substring(i+1);
    21.                 pointNum++;
    22.                 backTrack(s,i+2,pointNum);
    23.                 pointNum--;
    24.                 s=s.substring(0,i+1)+s.substring(i+2);
    25.                
    26.             }else{
    27.                 break;
    28.             }                      
    29.         }
    30.     }
    31.  
    32.     public boolean isVaild(String s,int start,int end){
    33.         if(start>end) return false;
    34.  
    35.         if(s.charAt(start)=='0'&&start!=end) return false;
    36.     
    37.         int num=0;
    38.         for(int i=start;i<=end;i++){
    39.             if(s.charAt(i)>9 || s.charAt(i)<0) return false;
    40.  
    41.            
    42.             num=num*10+s.charAt(start-'0');
    43.             if(num>255) return false;
    44.         }
    45.         return true;
    46.     }
    47. }

    78.子集

    给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

    说明：解集不能包含重复的子集。

    示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]

    1. class Solution {
    2.     List> result = new ArrayList<>();// 存放符合条件结果的集合
    3.     LinkedList path = new LinkedList<>();// 用来存放符合条件结果
    4.     public List> subsets(int[] nums) {
    5.         if (nums.length == 0){
    6.             result.add(new ArrayList<>());
    7.             return result;
    8.         }
    9.         subsetsHelper(nums, 0);
    10.         return result;
    11.     }
    12.  
    13.     private void subsetsHelper(int[] nums, int startIndex){
    14.         result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
    15.         if (startIndex >= nums.length){ //终止条件可不加
    16.             return;
    17.         }
    18.         for (int i = startIndex; i < nums.length; i++){
    19.             path.add(nums[i]);
    20.             subsetsHelper(nums, i + 1);
    21.             path.removeLast();
    22.         }
    23.     }
    24. }

     90. 子集 II

    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

    解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

    示例 1：

    输入：nums = [1,2,2]
    输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
    示例 2：

    输入：nums = [0]
    输出：[[],[0]]

    1. //这题重点在去重 去重要排序！ 去重有两种方法第一是直接i > start && nums[i - 1] == nums[i]判断
    2. class Solution {
    3.  
    4.   List> res = new ArrayList<>();
    5.   LinkedList path = new LinkedList<>();
    6.   
    7.   public List> subsetsWithDup( int[] nums ) {
    8.     Arrays.sort( nums );
    9.     subsetsWithDupHelper( nums, 0 );
    10.     return res;
    11.   }
    12.  
    13.  
    14.   private void subsetsWithDupHelper( int[] nums, int start ) {
    15.     res.add( new ArrayList<>( path ) );
    16.  
    17.     for ( int i = start; i < nums.length; i++ ) {
    18.         // 跳过当前树层使用过的、相同的元素
    19.       if ( i > start && nums[i - 1] == nums[i] ) {
    20.         continue;
    21.       }
    22.       path.add( nums[i] );
    23.       subsetsWithDupHelper( nums, i + 1 );
    24.       path.removeLast();
    25.     }
    26.   }
    27.  
    28. }
    29.  
    30. //使用user数组判断
    31. class Solution {
    32.    List> res= new ArrayList<>();// 存放符合条件结果的集合
    33.    LinkedList path = new LinkedList<>();// 用来存放符合条件结果
    34.    boolean[] used;
    35.     public List> subsetsWithDup(int[] nums) {
    36.         if (nums.length == 0){
    37.             result.add(path);
    38.             return res;
    39.         }
    40.         Arrays.sort(nums);
    41.         used = new boolean[nums.length];
    42.         subsetsWithDupHelper(nums, 0);
    43.         return result;
    44.     }
    45.     
    46.     private void subsetsWithDupHelper(int[] nums, int startIndex){
    47.         res.add(new ArrayList<>(path));
    48.        
    49.         for (int i = startIndex; i < nums.length; i++){
    50.             if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
    51.                 continue;
    52.             }
    53.             path.add(nums[i]);
    54.             used[i] = true;
    55.             subsetsWithDupHelper(nums, i + 1);
    56.             path.removeLast();
    57.             used[i] = false;
    58.         }
    59.     }
    60. }

    491. 递增子序列

    给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

    数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

    示例 1：

    输入：nums = [4,6,7,7]
    输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
    示例 2：

    输入：nums = [4,4,3,2,1]
    输出：[[4,4]]

    1. //这题和前面去重方法不一样 因为它要找出递增序列 不能进行排序!path.isEmpty()&&nums[i]
    2. class Solution {
    3.      List> res = new ArrayList<>();
    4.      LinkedList path = new LinkedList<>();
    5.      
    6.     public List> findSubsequences(int[] nums) {
    7.  
    8.        
    9.  
    10.         backTrack(nums,0);
    11.  
    12.         return res;
    13.     }
    14.  
    15.     public void backTrack(int[] nums,int startIndex){
    16.         if(path.size()>=2){
    17.             res.add(new ArrayList<>(path));
    18.             
    19.         }
    20.  
    21.         int[] user=new int[201];
    22.         for(int i=startIndex;i
    23.             if(!path.isEmpty()&&nums[i]1) || user[nums[i]+100]==1){
    24.                 continue;
    25.             }
    26.  
    27.             user[nums[i]+100]=1;
    28.             path.add(nums[i]);
    29.            
    30.             backTrack(nums,i+1);
    31.             path.removeLast();
    32.             
    33.         }
    34.     }
    35. }

    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]]

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     LinkedList path=new LinkedList<>();
    4.     
    5.     public List> permute(int[] nums) {
    6.  
    7.         backTrack(nums);
    8.         return res;
    9.     }
    10.  
    11.     public void backTrack(int[] nums){
    12.         if(path.size()==nums.length){
    13.             res.add(new ArrayList<>(path));
    14.         }
    15.  
    16.         for(int i=0;i
    17.             if(path.contains(nums[i])) continue;
    18.             path.add(nums[i]);
    19.             backTrack(nums);
    20.             path.removeLast();
    21.         }
    22.     }
    23. }

    47. 全排列 II

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     LinkedList path=new LinkedList<>();
    4.     boolean[] user;
    5.     public List> permuteUnique(int[] nums) {
    6.         
    7.         user=new boolean[nums.length];
    8.        
    9.         Arrays.sort(nums);
    10.         backTrack(nums);
    11.         return res;
    12.     }
    13.  
    14.     public void backTrack(int[] nums){
    15.         if(path.size()==nums.length){
    16.             res.add(new ArrayList<>(path));
    17.            
    18.         }
    19.  
    20.         for(int i=0;i
    21.             if(i>0&&nums[i]==nums[i-1]&&user[i-1]==false) continue;
    22.  
    23.             if(user[i]==false){
    24.                 user[i]=true;
    25.                 path.add(nums[i]);
    26.             
    27.                 backTrack(nums);
    28.                 path.removeLast();
    29.                 user[i]=false;
    30.             }
    31.         }
    32.     }
    33. }

    51. N 皇后

    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    示例 1：

    输入：n = 4
    输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    解释：如上图所示，4 皇后问题存在两个不同的解法。
    示例 2：

    输入：n = 1
    输出：[["Q"]]

    1. class Solution {
    2.     List> res=new ArrayList<>();
    3.     
    4.     public List> solveNQueens(int n) {
    5.         char[][] board=new char[n][n];
    6.  
    7.         for(char[] c:board){
    8.             Arrays.fill(c,'.');
    9.         }
    10.  
    11.         backTrack(n,0,board);
    12.  
    13.         return res;
    14.     }
    15.  
    16.     public void backTrack(int n,int row,char[][] board){
    17.         if(row==n){
    18.             res.add(ArrayList(board));
    19.             return;
    20.         }
    21.         for(int col=0;col
    22.             if(isVaild(row,col,n,board)){
    23.                 board[row][col]='Q';
    24.                 backTrack(n,row+1,board);
    25.                 board[row][col]='.';
    26.             }
    27.         }
    28.     }
    29.  
    30.     public List ArrayList(char[][] board){
    31.             List list=new ArrayList<>();
    32.             for(char[] c:board){
    33.                 list.add(String.copyValueOf(c));
    34.             }
    35.             return list;
    36.     }
    37.  
    38.         public boolean isVaild(int row,int col,int n,char[][] board){
    39.             //列
    40.             for(int i=0;i
    41.                 if(board[i][col]=='Q'){
    42.                     return false;
    43.                 }
    44.             }
    45.  
    46.             //45°
    47.             for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
    48.                 if(board[i][j]=='Q'){
    49.                     return false;
    50.                 }
    51.             }
    52.             //135°
    53.             for(int i=row-1,j=col+1;i>=0&&j
    54.                 if(board[i][j]=='Q'){
    55.                     return false;
    56.                 }
    57.             }
    58.             return true;
    59.         }
    60. }

  • 相关阅读:
    JAVA:实现Floyd Triangle弗洛伊德三角算法(附完整源码)
    Unity游戏Mod/插件制作教程06 - Harmony补丁基础
    Maven下导入jar包的几种方式
    序列化--Serial
    python爬虫（Selenium案列）第二十四
    C++之智能指针shared_ptr死锁问题(二百)
    Hyperledger Fabric 2.2 学习笔记：测试网络test-network
    基类、接口、抽象类的区别
    【数学建模】单、多因素试验的方差分析（Matlab代码实现）
    【maven私库nexus开机自启动】
  • 原文地址：https://blog.csdn.net/weixin_46345400/article/details/126339138