39. 组合总和

力扣题目链接

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

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

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

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

解题思路

1. 优化手段，先排序。在遍历的时候，可以判断 if (sum + candidates[i] > target) break;
2. res.add(new ArrayList<>(path));，添加到结果集的时候，要新创建数组，否则引用会被接下来的代码逻辑处理。

Java实现

class Solution_LC39 {List> res = new ArrayList<>();LinkedList path = new LinkedList<>();public List> combinationSum(int[] candidates, int target) {backtrack(candidates, target, 0, 0);return res;}private void backtrack(int[] candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {sum += candidates[i];path.add(candidates[i]);backtrack(candidates, target, sum, i);sum -= candidates[i];path.removeLast();}}}

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. 允许结果集里面数是一样的，但是索引不一样。核心就是将候选数组进行排序，判断i > startIndex && candidates[i] == candidates[i - 1]。i > startIndex实现了回溯的当前轮的首位元素可以和上一轮是相同的。如果元素在第一轮中已经选中了1，在下一个轮次是可以继续选择1的，因为数组中存在两个1。candidates[i] == candidates[i - 1]这个是用来跳过轮次的，因为选择到1,2,7，会选择同一轮次中的1两次。
2. 不能使用HashSet进行去重，因为元素1在数组中出现两次，就意味着在结果集中可以出现两个1。

Java实现

class Solution {List> res = new ArrayList<>();LinkedList path = new LinkedList<>();public List> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates, target, 0, 0);return res;}private void backtrack(int[] candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {if (i > startIndex && candidates[i] == candidates[i - 1]) {continue;}sum += candidates[i];path.add(candidates[i]);backtrack(candidates, target, sum, i + 1);sum -= candidates[i];path.removeLast();}}
}

131.分割回文串

力扣题目链接

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

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

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

解决思路

1. 判断字符串是否回文，根据双指针
2. 字符串切分，startIndex是起始位置，i是终止位置，substring(start,end)是不包含末尾字符的。

Java实现

class Solution_LC131 {List> res = new ArrayList<>();LinkedList path = new LinkedList<>();public List> partition(String s) {backtrack(s, 0);return res;}private void backtrack(String s, int startIndex) {if (startIndex == s.length()) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);path.add(str);backtrack(s, i + 1);path.removeLast();}}}private boolean isPalindrome(String s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}

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. isValid用来判断字符串是否有效，当数字不超过255，数字不是0，是不能用0开头的，数字的所有字符不能大于9和小于0。字符串转换数字。
2. 终止条件，当切割字符串正好为4且start等于s.length，回收结果集。
3. 回溯方法中参数增加切割次数
4. 回溯单层逻辑中，片段累增，结果集拼接字符串，增加分隔字符。回溯的逻辑：stringBuilder.delete(start + segNum, i + segNum + 2);，因为字符串是不断变化的，会添加.。且删除字符串是删除i-start长度的字符串，需要计算因为分隔segment，需要添加的分隔字符数，且回溯的时候还要删除一个字符数。

Java实现

class Solution_LC93 {List res = new ArrayList<>();StringBuilder stringBuilder = new StringBuilder();public List restoreIpAddresses(String s) {backtrack(s, 0, 0);return res;}private void backtrack(String s, int start, int segNum) {if (start == s.length() && segNum == 4) {res.add(stringBuilder.toString());return;}if (start == s.length() || segNum == 4) {return;}for (int i = start; i < s.length()& i - start < 3; i++) {if (isValid(s, start, i)) {stringBuilder.append(s.substring(start, i + 1));segNum++;if (segNum < 4) {stringBuilder.append(".");}backtrack(s, i + 1, segNum);segNum--;stringBuilder.delete(start + segNum, i + segNum + 2);}}}private Boolean isValid(String s, int start, int end) {if (start > end) {return false;}if (s.charAt(start) == '0' && start != end) {return false;}int num = 0;for (int i = start; i <= end; i++) {char c = s.charAt(i);if (c > '9' || c < '0') {return false;}num = num * 10 + s.charAt(i) - '0';if (num > 255) {return false;}}return true;}
}

78.子集

力扣题目链接

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

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

解决思路

1. 在每一个回溯中都进行回收结果集
2. startIndex：获取数组起始元素的索引。

Java实现

public class Solution_LC78 {List> res = new ArrayList<>();LinkedList path = new LinkedList<>();public List> subsets(int[] nums) {backtrack(nums, 0);return res;}private void backtrack(int[] nums, int startIndex) {res.add(new ArrayList<>(path));if (startIndex == nums.length) {return;}for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);backtrack(nums, i + 1);path.removeLast();}}}