给定一个整数数组 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精选题解
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. 递增子序列
难度中等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); } } }
难度中等2418收藏分享切换为英文接收动态反馈
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 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 地址
难度中等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); } }
