• LeetCode —— 回溯

    77. 组合

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

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

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

    216. 组合总和III

    找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：（1）只使用数字1到9；（2）每个数字 最多使用一次 。返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> combinationSum3(int k, int n) {
    6.         backTrack(k, n, 1, 0);
    7.         return list;
    8.     }
    9.  
    10.     public void backTrack(int k, int targetSum, int startIndex, int sum){
    11.         if(sum > targetSum || path.size() > k){
    12.             return;
    13.         }
    14.         if(path.size() == k && sum == targetSum){
    15.             list.add(new ArrayList<>(path));
    16.             return;
    17.         }
    18.  
    19.         for(int i = startIndex; i <= 9; i++){
    20.             path.add(i);
    21.             sum += i;
    22.             backTrack(k, targetSum, i + 1, sum);
    23.             path.removeLast();
    24.             sum -= i;
    25.         }
    26.     }
    27. }

    39.  组合总和

    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

    示例：输入：candidates = [2,3,6,7], target = 7         输出：[[2,2,3],[7]]

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

    40. 组合总和II

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

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

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> combinationSum2(int[] candidates, int target) {
    6.         Arrays.sort(candidates);
    7.         backTrack(candidates, target, 0, 0);
    8.         return list;
    9.     }
    10.  
    11.     public void backTrack(int[] candidates, int target, int startIndex, int sum){
    12.         if(sum == target){
    13.             list.add(new ArrayList<>(path));
    14.             return;
    15.         }
    16.  
    17.         for(int i = startIndex; i < candidates.length; i++){
    18.             if(sum + candidates[i] > target){
    19.                 break;
    20.             }
    21.             // 跳过同一层使用过的元素（必须在数组有序时才可以这样使用）
    22.             if(i > startIndex && candidates[i] == candidates[i - 1]){
    23.                 continue;
    24.             }
    25.             path.add(candidates[i]);
    26.             sum += candidates[i];
    27.             backTrack(candidates, target, i + 1, sum);
    28.             sum -= candidates[i];
    29.             path.removeLast();
    30.         }
    31.     }
    32. }
    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> combinationSum2(int[] candidates, int target) {
    6.         Arrays.sort(candidates);
    7.         back(candidates, target, 0, 0);
    8.         return list;
    9.     }
    10.  
    11.     public void back(int[] candidates, int target, int startIndex, int sum){
    12.         if(sum > target){
    13.             return;
    14.         }
    15.         if(sum == target){
    16.             list.add(new ArrayList<>(path));
    17.             return;
    18.         }
    19.         
    20.         Set set = new HashSet<>();
    21.         for(int i = startIndex; i < candidates.length; i++){
    22.             if(set.contains(candidates[i])){
    23.                 continue;
    24.             }
    25.             set.add(candidates[i]);
    26.             path.add(candidates[i]);
    27.             sum += candidates[i];
    28.             back(candidates, target, i + 1, sum);
    29.             sum -= candidates[i];
    30.             path.removeLast();
    31.         }
    32.     }
    33. }

    17. 电话号码的字母组合

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

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

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

    1. class Solution {
    2.     List list = new ArrayList<>();
    3.     StringBuilder item = new StringBuilder();
    4.  
    5.     public List letterCombinations(String digits) {
    6.         if(digits.length() == 0){
    7.             return list;
    8.         }
    9.         String[] numberString = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    10.         backTrack(digits, numberString, 0);
    11.         return list;
    12.     }
    13.  
    14.     public void backTrack(String digits, String[] numberString, int index){
    15.         if(item.length() == digits.length()){
    16.             list.add(item.toString());
    17.             return;
    18.         }
    19.  
    20.         String cur = numberString[digits.charAt(index) - '0'];
    21.         for(int i = 0; i < cur.length(); i++){
    22.             item.append(cur.charAt(i));
    23.             backTrack(digits, numberString, index + 1);
    24.             item.deleteCharAt(item.length() - 1);
    25.         }
    26.     }
    27. }

     131. 分割回文子串

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

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

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList item = new LinkedList<>();
    4.  
    5.     public List> partition(String s) {
    6.         backTrack(s, 0);
    7.         return list;
    8.     }
    9.  
    10.     public void backTrack(String s, int startIndex){
    11.         if(startIndex >= s.length()){
    12.             list.add(new ArrayList<>(item));
    13.             return;
    14.         }
    15.         for(int i = startIndex; i < s.length(); i++){
    16.             if(!isPalindrome(s, startIndex, i)){
    17.                 continue;
    18.             }
    19.             item.add(s.substring(startIndex, i + 1));
    20.             backTrack(s, i + 1);
    21.             item.removeLast();
    22.         }
    23.     }
    24.  
    25.     public boolean isPalindrome(String s, int left, int right){
    26.         while(left <= right){
    27.             if(s.charAt(left) != s.charAt(right)){
    28.                 return false;
    29.             }
    30.             left++;
    31.             right--;
    32.         }
    33.         return true;
    34.     }
    35. }

    78. 子集

    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> subsets(int[] nums) {
    6.         backTrack(nums, 0);
    7.         return list;
    8.     }
    9.  
    10.     public void backTrack(int[] nums, int startIndex){
    11.         list.add(new ArrayList<>(path));
    12.         if(startIndex >= nums.length){   // 可以省略
    13.             return;
    14.         }
    15.         for(int i = startIndex; i < nums.length; i++){
    16.             path.add(nums[i]);
    17.             backTrack(nums, i + 1);
    18.             path.removeLast();
    19.         }
    20.     }
    21. }

    90. 子集II

    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

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

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> subsetsWithDup(int[] nums) {
    6.         Arrays.sort(nums);
    7.         backTrack(nums, 0);
    8.         return list;
    9.     }
    10.  
    11.     public void backTrack(int[] nums, int startIndex){
    12.         list.add(new ArrayList<>(path));
    13.         if(startIndex >= nums.length){    // 可以省略
    14.             return;
    15.         }
    16.  
    17.         for(int i = startIndex; i < nums.length; i++){
    18.             if(i > startIndex && nums[i] == nums[i - 1]){
    19.                 continue;
    20.             }
    21.             path.add(nums[i]);
    22.             backTrack(nums, i + 1);
    23.             path.removeLast();
    24.         }
    25.     }
    26. }
    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> subsetsWithDup(int[] nums) {
    6.         Arrays.sort(nums);
    7.         backTrack(nums, 0);
    8.         return list;
    9.     }
    10.  
    11.     public void backTrack(int[] nums, int startIndex){
    12.         list.add(new ArrayList<>(path));
    13.         if(startIndex >= nums.length){
    14.             return;
    15.         }
    16.  
    17.         Set set = new HashSet<>();
    18.         for(int i = startIndex; i < nums.length; i++){
    19.             if(set.contains(nums[i])){
    20.                 continue;
    21.             }
    22.             set.add(nums[i]);
    23.             path.add(nums[i]);
    24.             backTrack(nums, i + 1);
    25.             path.removeLast();
    26.         }
    27.     }
    28. }

    491. 递增子序列

    给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

    示例：输入：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]]

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.     LinkedList path = new LinkedList<>();
    4.  
    5.     public List> findSubsequences(int[] nums) {
    6.         backTrack(nums, 0);
    7.         return list;
    8.     }
    9.  
    10.     public void backTrack(int[] nums, int startIndex){
    11.         if(path.size() >= 2){
    12.             list.add(new ArrayList<>(path));
    13.         }
    14.  
    15.         // 由于数组无序，因此不能使用 if(i > startIndex && nums[i] == nums[i - 1])
    16.         HashSet set = new HashSet<>();
    17.         for(int i = startIndex; i < nums.length; i++){
    18.             if((!path.isEmpty() && nums[i] < path.getLast()) || set.contains(nums[i])){
    19.                 continue;
    20.             }
    21.             set.add(nums[i]);
    22.             path.add(nums[i]);
    23.             backTrack(nums, i + 1);
    24.             path.removeLast();
    25.         }
    26.     }
    27. }

    46. 全排列

    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

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

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

    47. 全排列II

    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

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

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

    93. 复原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 地址。

    给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

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

    1. class Solution {
    2.     List list = new ArrayList<>();
    3.  
    4.     public List restoreIpAddresses(String s) {
    5.         if(s.length() > 12){
    6.             return list;
    7.         }
    8.  
    9.         backTrack(s, 0, 0);
    10.         return list;
    11.     }
    12.  
    13.     public void backTrack(String s, int startIndex, int pointNum){
    14.         if(pointNum == 3){   // 分割数量为3时，分隔结束
    15.             if(isValid(s, startIndex, s.length() - 1)){   // 判断第四段⼦字符串是否合法
    16.                 list.add(s);
    17.             }
    18.             return;
    19.         }
    20.  
    21.         for(int i = startIndex; i < s.length(); i++){
    22.             if(!isValid(s, startIndex, i)){
    23.                 continue;
    24.             }
    25.             s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个点
    26.             pointNum++;
    27.             backTrack(s, i + 2, pointNum);     // 插⼊点之后下⼀个⼦串的起始位置为i+2
    28.             pointNum--;     // 回溯
    29.             s = s.substring(0, i + 1) + s.substring(i + 2);    // 回溯删掉逗点
    30.         }
    31.     }
    32.  
    33.     public Boolean isValid(String s, int left, int right) {
    34.         if (left > right) {
    35.             return false;
    36.         }
    37.         if (s.charAt(left) == '0' && left != right) {   // 0开头的数字不合法
    38.             return false;
    39.         }
    40.         int num = 0;
    41.         for (int i = left; i <= right; i++) {
    42.             num = num * 10 + (s.charAt(i) - '0');
    43.             if (num > 255) { // 如果⼤于255了不合法
    44.                 return false;
    45.             }
    46.         }
    47.         return true;
    48.     }
    49. }

    51. N皇后

    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    示例：输入：n = 4         输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

    1. class Solution {
    2.     List> list = new ArrayList<>();
    3.  
    4.     public List> solveNQueens(int n) {
    5.         char[][] matrix = new char[n][n];
    6.         for(char[] array : matrix){
    7.             Arrays.fill(array, '.');
    8.         }
    9.         backTrack(n, 0, matrix);
    10.         return list;
    11.     }
    12.  
    13.     public void backTrack(int n, int row, char[][] matrix){
    14.         if(row == n){
    15.             List item = new ArrayList<>();
    16.             for(char[] array : matrix){
    17.                 item.add(String.valueOf(array));
    18.             }
    19.             list.add(item);
    20.             return;
    21.         }
    22.  
    23.         for(int column = 0; column < n; column++){
    24.             if(isValid(row, column, n, matrix)){
    25.                 matrix[row][column] = 'Q';
    26.                 backTrack(n, row + 1, matrix);
    27.                 matrix[row][column] = '.';
    28.             }
    29.         }
    30.     }
    31.  
    32.     public boolean isValid(int row, int column, int n, char[][] matrix) {
    33.         // 检查列
    34.         for(int i = 0; i < row; i++){
    35.             if(matrix[i][column] == 'Q'){
    36.                 return false;
    37.             }
    38.         }
    39.  
    40.         // 检查45度对角线
    41.         for(int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
    42.             if(matrix[i][j] == 'Q'){
    43.                 return false;
    44.             }
    45.         }
    46.  
    47.         // 检查135度对角线
    48.         for(int i = row - 1, j = column + 1; i >= 0 && j <= n-1; i--, j++){
    49.             if(matrix[i][j] == 'Q'){
    50.                 return false;
    51.             }
    52.         }
    53.         return true;
    54.     }
    55. }
  • 相关阅读:
    股票交易接口list接口索引的方法
    CleanMyMac4.11.3macOS系统垃圾清理应用
    论文研读：ViT-V-Net—用于无监督3D医学图像配准的Vision Transformer
    一种用于Linux内核驱动开发的Vim环境配置
    记一次 ClickHouse 性能测试
    Java--web.xml加载过程；文件标签详解
    “次世代”究竟是什么？次世代角色建模又该怎么学？
    使用 Temporal Fusion Transformer 进行时间序列预测
    SQL练习：表妹不在，没人帮我查表，只好自己来了
    WebGL开发数据可视化应用
  • 原文地址：https://blog.csdn.net/Archer__13/article/details/133391922