for循环横向遍历，递归纵向遍历，回溯不断调整结果集
画树，回溯要画树
77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
result.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。
class Solution { LinkedList path = new LinkedList(); List<List> result = new ArrayList(); public List<List> combine(int n, int k) { backTracking(n,k,1); return result; } void backTracking(int n, int k, int startIndex){ if(path.size()==k){ result.add(new ArrayList(path)); return; } for (int i = startIndex; i <= n; i++) { path.add(i); backTracking(n,k,i+1); path.removeLast();//回溯 } }}剪枝操作优化代码：
for (int i = startIndex; i <= n; i++) {剪枝：
for (int i = startIndex; i <=n-(k-path.size())+1; i++) {path.size() 是当前路径里元素的个数
k-path.size() 是还需要的元素个数
n-(k-path.size())+1 至多走到哪里
216. 组合总和 III
找出所有相加之和为n 的k个数的组合，且满足下列条件：
只使用数字1到9
每个数字最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
- 这题和上面一题十分相似，就浅浅改了一下上面的代码
class Solution { LinkedList path = new LinkedList(); List<List> result = new ArrayList(); public List<List> combinationSum3(int k, int n) { if(k > n){//如果n小于k的话直接返回 return result; } backTracking(k,n,1); return result; } void backTracking(int k, int n, int startIndex){ if(path.size()==k){//数组的长度达到标准之后 int sum = 0; for (Integer p : path) { sum +=p; } if(sum == n){//看数组中数字之和是否达到标准 result.add(new ArrayList(path)); } return; } for (int i = startIndex; i <= n; i++) { path.add(i); backTracking(k,n,i+1); path.removeLast(); } }}- 结果超出时间限制，因为没有剪枝
for (int i = startIndex; i <= Math.min(n-(k*(k-1)/2),9) ; i++) {- k*(k-1)/2 是对前k-1个数的求和
- n-(k*(k-1)/2) 和 9 取最小是怕n太大，k太小导致path里的数 > 9
17. 电话号码的字母组合
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
- 把按键上对应的数字转换成字符串letters，遍历的时候要遍历的是字符串
class Solution { List result = new ArrayList(); static String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//下标就是按键上的数字 public List letterCombinations(String digits) { if(digits.equals("")) return result;//对特殊情况特殊处理 backTracking(digits,0);//从零开始 return result; } static StringBuilder sb = new StringBuilder(); void backTracking(String digits, int index){ //index指的是当前对哪个数字进行处理 if(sb.length()==digits.length()){ result.add(sb.toString()); return; } String letter = letters[(digits.charAt(index))-'0'];//取当前下标对应的字符串 for (int i = 0; i < letter.length(); i++) { sb.append(letter.charAt(i)); backTracking(digits,index+1); sb.deleteCharAt(sb.length()-1); } }}- 感觉慢慢理解回溯了?
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
- 对组合问题的变形：允许元素重复使用，不固定路径数组的长度
class Solution { List<List> res = new ArrayList(); List path = new ArrayList(); public List<List> combinationSum(int[] candidates, int target) { combine(candidates, target, 0); return res; } void combine(int[] candidates, int target, int startIndex){ int sum = 0; //算出当前路径的结点之和 for (Integer node : path) { sum += node; } if(sum == target){ res.add(new ArrayList(path));//得到符合条件的结果，把路径加到结果集中 return; } if(sum > target){ return;//当前路径上的结点之和已经大于所求，不用再往下加了 } for (int i = startIndex; i < candidates.length; i++) { path.add(candidates[i]);//把当前的元素加入path中 combine(candidates,target,i); path.remove(path.size()-1); } }}40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
- 本题也是对组合问题的变形：candidates中的元素 无序 且 重复
- 元素无序 给剪枝操作增加了难度，我在操作前对数组candidates进行了排序
- 元素重复 我的做法是对结果集res 新建了一个result进行去重，但是有的测试用例超时
class Solution { List<List> res = new ArrayList(); List path = new ArrayList(); public List<List> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates);//先给数组排序 int length = candidates.length; for (int candidate : candidates) { if(candidate > target){ length--; } } Arrays.copyOf(candidates,length); combine(candidates, target, 0); //此时已经拿到结果集res,但是需要对其进行去重操作 List<List> result = new ArrayList(); for (List re : res) { if (!result.contains(re)){ result.add(re);//如果真正的结果集result中不包括re，就可以把re加入道result } } return result; } void combine(int[] candidates, int target, int startIndex){ int sum = 0; //算出当前路径的结点之和 for (Integer node : path) { sum += node; } if(sum == target){ res.add(new ArrayList(path));//得到符合条件的结果，把路径加到结果集中 return; } if(sum > target){ return;//当前路径上的结点之和已经大于所求，不用再往下加了 } for (int i = startIndex; i < candidates.length; i++) { path.add(candidates[i]);//把当前的元素加入path中 combine(candidates,target,i+1); path.remove(path.size()-1); } }}- 就是这个用例超时，仔细瞅瞅这个用例，它说要对重复的数据进行处理，而不能只改结果集。确实，那样效率太低了?
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]30- 我在for循环中加入了如下语句，想使重复的元素跳出当前循环
if(i>0&&candidates[i]==candidates[i-1]){ continue;}- 但是他把满足条件的含有重复元素的结果也给剪掉了，是剪枝的条件出了问题
- 把 i>0 换成 i>startIndex 后运行通过
if(i>startIndex&&candidates[i]==candidates[i-1]){131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
- 这题是分割问题，但是本质和组合问题思路一样
- 剪枝的思路是：如果当前切出来的子串已经不是回文串了，就continue进入下一次循环，这样可以保证叶子结点都是满足要求的path
class Solution { List<List> res = new ArrayList(); LinkedList path = new LinkedList(); public List<List> partition(String s) { combine(s,0); return res; } void combine(String s, int startIndex){ if(startIndex >= s.length()){ res.add(new LinkedList(path));//收获叶子结点 } for (int i = startIndex; i endIndex){ return true; } if(s.charAt(startIndex)==s.charAt(endIndex)){ startIndex++; endIndex--; } else { return false; } } }}93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
❗ ❗ ❗ 不是自己写出来的
- 按照自己本来的思路写，是new了一个StringBuilder，想着这样操作方便些，但是很难回溯啊，就把自己绕进去了，下面的题解是在String上用subString()的方法操作
- 还有递归出口，要专门创建一个int去记录逗点的数量
class Solution { List result = new ArrayList(); public List restoreIpAddresses(String s) { if (s.length() > 12) return result; // 算是剪枝了 backTrack(s, 0, 0); return result; } // startIndex: 搜索的起始位置， pointNum:添加逗点的数量 private void backTrack(String s, int startIndex, int pointNum) { if (pointNum == 3) {// 逗点数量为3时，分隔结束 // 判断第四段⼦字符串是否合法，如果合法就放进result中 if (isValid(s,startIndex,s.length()-1)) { result.add(s); } return; } for (int i = startIndex; i end) { return false; } if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法 return false; } int num = 0; for (int i = start; i '9' || s.charAt(i) 255) { // 如果⼤于255了不合法 return false; } } return true; }}- 回溯是把当前for循环里的操作给回溯掉，干干净净的进入下一个循环
- 感觉这一题是挺难的，现在还有点没迷过来?
78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution { LinkedList path = new LinkedList(); List<List> res = new LinkedList(); public List<List> subsets(int[] nums) { res.add(new LinkedList(path));//把空的path进去 combine(nums,0); return res; } void combine(int[] nums, int startIndex){ if(!path.isEmpty()&&path.getLast()==nums[nums.length-1]){ return;//递归出口 } for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); res.add(new LinkedList(path));//每一个结点都要收集 combine(nums,i+1); path.removeLast();//回溯 } }}- 这题比较简单，子集的特点就是每一个结点都要收集，那我们在添加路径时收集就可以了
- 递归的出口是当path最后一个数是数组中的最后一个数时，不再向下递归
90. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
- 这题和之前相比就多了一个去重操作，先排序后去重
class Solution { LinkedList path = new LinkedList(); List<List> res = new LinkedList(); public List<List> subsetsWithDup(int[] nums) { res.add(new LinkedList(path));//把空的path进去 Arrays.sort(nums);//先排序 combine(nums,0); return res; } void combine(int[] nums, int startIndex){ for (int i = startIndex; i startIndex && nums[i] == nums[i - 1]) { continue;//去重 } path.add(nums[i]); res.add(new LinkedList(path));//每一个结点都要收集 combine(nums,i+1); path.removeLast();//回溯 } }}491. 递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
class Solution { List<List> res = new ArrayList(); ArrayList path = new ArrayList(); public List<List> findSubsequences(int[] nums) { combine(nums, 0); return res; } void combine(int[] nums, int startIndex) { if (path.size() > 1) { res.add(new ArrayList(path)); } Map map = new HashMap();//每层一个map for (int i = startIndex; i < nums.length; i++) { if (!path.isEmpty() && nums[i] 0){//如果该元素的value不是0，说明之前添加过，直接进下一次循环 continue;//去重 } map.put(nums[i],map.getOrDefault(nums[i],0)+1);//第一次遍历到该元素时，以数组元素为key，value赋1 path.add(nums[i]); combine(nums, i + 1); path.remove(path.size() - 1);//回溯 } }}- 这里去重是用map实现的
default V getOrDefault ( Object key , V defaultValue ) 返回指定key映射到的value，如果当前map不包含当前key的映射，则返回 defaultValue 。
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
全排列问题 还是要画树
循环遍历当前path中没有的数
List<List> res = new ArrayList(); List path = new ArrayList(); public List<List> permute(int[] nums) { combine(nums); return res; } void combine(int[] nums){ if (path.size()== nums.length){ res.add(new ArrayList(path));//收集结果 } for (int num : nums) { if (path.contains(num)) { continue;//如果路径里有num，跳出此次循环 } path.add(num); combine(nums); path.remove(path.size()-1); } }47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
只做树层的去重，不做树枝的去重
nums[i]=nums[i-1]并且used[i-1]=true说明nums[i-1]已经被加进了path中，这是数枝的重复
nums[i]=nums[i-1]并且used[i-1]=false说明nums[i-1]已经被回溯成了false，这是树层的重复，要剪掉✂
新建了一个used数组来表示nums数组的使用情况
class Solution { List<List> res = new ArrayList(); List path = new ArrayList(); boolean[] used; public List<List> permuteUnique(int[] nums) { used = new boolean[nums.length]; for (boolean b : used) { b=false; } Arrays.sort(nums); comine(nums,used); return res; } void comine(int[] nums, boolean[] used) { if (path.size() == nums.length) { res.add(new ArrayList(path));//收集结果 } for (int i = 0; i 0&&nums[i]==nums[i-1]&&used[i-1]==false) { continue;//当前数和前面的数相等并且前面的数还未使用时 } if(used[i]==false){//当前元素还未使用时 path.add(nums[i]); used[i]=true;//在path中添加元素，该位置标记为true comine(nums,used); path.remove(path.size() - 1);//回溯 used[i]=false;//回溯 } } }}