回溯算法编程题集合（leetcode)

Love The Way You Lie 2023-09-26 20:11 133阅读 0赞

> 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
> 
> 示例 1：
> 
> 输入： nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
> 输出： True  
> 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。  
> 示例 2:
> 
> 输入: nums = \[1,2,3,4\], k = 3  
> 输出: false
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets

本题一开始本人打算使用动态规划，一开始的思路是求得nums数组的和然后除以k赋值为target，然后利用动态规划01背包求nums数组中可以组成target的方案数，但是运用此题理解有偏差，因为是划分子集所以有些数组元素不能重复使用。

选用leetcode精选题解

[力扣][Link 1]

public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for (int i = 0; i < nums.length; i++) sum += nums[i];
            if (sum % k != 0) return false;
            int target = sum / k;
            // 排序优化
            Arrays.sort(nums);
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
                r--;
            }
            return backtrack(nums, 0, new int[k], k, target);
        }
        private boolean backtrack(int[] nums, int index, int[] bucket, int k, int target) {
            // 结束条件优化
            if (index == nums.length) return true;
            for (int i = 0; i < k; i++) {
                // 优化点二
                if (i > 0 && bucket[i] == bucket[i - 1]) continue;
                // 剪枝
                if (bucket[i] + nums[index] > target) continue;
                bucket[i] += nums[index];
                if (backtrack(nums, index + 1, bucket, k, target)) return true;
                bucket[i] -= nums[index];
            }
            return false;
        }

> [491. 递增子序列][491.]
> 
> 难度中等639收藏分享切换为英文接收动态反馈
> 
> 给你一个整数数组 `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]]

public static List<List<Integer>> findSubsequences(int[] nums) {
            List<List<Integer>> lists=new ArrayList<>();
            if(nums.length<2)
                return lists;
            List<Integer> list=new ArrayList<>();
            backtreeing(lists,list,0,nums);
            return lists;
    
        }
        public static void backtreeing(List<List<Integer>> lists,List<Integer> list,int start,int nums[]){
             if(list.size()>=2){
                 lists.add(new ArrayList<>(list));
             }
             //set做树层剪枝，同一层已经使用过的元素再此使用就跳出
            HashSet<Integer> set=new HashSet<>();
            for(int i=start;i<nums.length;i++){
                if(i>start&&set.contains(nums[i]))
                    continue;
                if(list.size()==0||nums[i]>=list.get(list.size()-1)){
                    list.add(nums[i]);
                    set.add(nums[i]);
                    backtreeing(lists,list,i+1,nums);
                    list.remove(list.size()-1);
                }
    
            }
        }

> [17. 电话号码的字母组合][17.]
> 
> 难度中等2418收藏分享切换为英文接收动态反馈
> 
> 给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按 **任意顺序** 返回。
> 
> 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
> 
> ![711e62888bbd0451bcb45ff69411bc74.png][]
> 
> **示例 1：**
> 
>     输入：digits = "23"
>     输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
> 
> **示例 2：**
> 
>     输入：digits = ""
>     输出：[]
> 
> **示例 3：**
> 
>     输入：digits = "2"
>     输出：["a","b","c"]

public List<String> letterCombinations(String digits) {
            List<String> list=new ArrayList<>();
            if(digits==null||digits.length()==0)
                return list;
            char[] chars = digits.toCharArray();
            StringBuilder stringBuilder=new StringBuilder();
            Map<Character, String> phoneMap = new HashMap<Character, String>() {
       {
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtreeing(chars,list,phoneMap,stringBuilder,0);
            return list;
        }
        public void backtreeing(char[] chars,List<String> list,Map<Character,String> map,   StringBuilder stringBuilder,int start){
           if(start==chars.length){
               list.add(stringBuilder.toString());
               return;
           }
            String s1 = map.get(chars[start]);
            for(int i=0;i<s1.length();i++){
               stringBuilder.append(s1.charAt(i));
               backtreeing(chars,list,map,stringBuilder,start+1);
               stringBuilder.deleteCharAt(stringBuilder.length()-1);
           }
        }

> [93. 复原 IP 地址][93. _ IP]
> 
> 难度中等1203收藏分享切换为英文接收动态反馈
> 
> **有效 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` 中的任何数字。你可以按 **任何** 顺序返回答案。
> 
> **示例 1：**
> 
>     输入：s = "25525511135"
>     输出：["255.255.11.135","255.255.111.35"]
> 
> **示例 2：**
> 
>     输入：s = "0000"
>     输出：["0.0.0.0"]
> 
> **示例 3：**
> 
>     输入：s = "101023"
>     输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

public static List<String> restoreIpAddresses(String s) {
            List<String> list=new ArrayList<>();
            if(s.length()<4)
                return list;
            String[] num=new String[4];
            backtreeing(s,list,0,0,num);
            return list;
        }
        public static void backtreeing(String s,List<String> list,int start,int count,String[] num){
            if(count==4){
                if(start==s.length()){
                    StringBuilder stringBuilder=new StringBuilder();
                    for(int i=0;i<num.length;i++){
                       stringBuilder.append(num[i]);
                       if(i!=3)
                           stringBuilder.append(".");
                    }
                    list.add(stringBuilder.toString());
                }
                return;
            }
            //if 语句不能放在外面因为在执行过程中start会超出字符串长度，导致异常，比如10.10.23 count=3,start=6的时候就会错误
    //        if(s.charAt(start)=='0'){
    //            num[count] = "0";
    //            backtreeing(s, list, start + 1, count + 1, num);
    //            return;
    //        }
    
            StringBuilder stringBuilder=new StringBuilder();
            for(int i=start;i<s.length();i++){
                if(s.charAt(start)=='0'){
                    num[count] = "0";
                    backtreeing(s, list, start + 1, count + 1, num);
                    return;
                }
                if(i>start+2)
                    break;
                String substring = s.substring(start, i + 1);
                if(Integer.parseInt(substring)>255)
                    continue;
                stringBuilder.append(substring);
                num[count]=stringBuilder.toString();
                backtreeing(s,list,i+1,count+1,num);
                 stringBuilder.delete(0,stringBuilder.length()+1);
            }
    
        }

[Link 1]: https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-lfool-d9o7/
[491.]: https://leetcode.cn/problems/non-decreasing-subsequences/
[17.]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
[711e62888bbd0451bcb45ff69411bc74.png]: https://img-blog.csdnimg.cn/img_convert/711e62888bbd0451bcb45ff69411bc74.png
[93. _ IP]: https://leetcode.cn/problems/restore-ip-addresses/