- 组合问题模板算法
- 组合问题分类
- 组合问题题单
- LeetCode-17.电话号码的字母组合 ">LeetCode-17.电话号码的字母组合
- LeetCode-22.括号生成 ">LeetCode-22.括号生成
- LeetCode-39.组合总和">LeetCode-39.组合总和
- LeetCode-40.组合总和 II ">LeetCode-40.组合总和 II
- LeetCode-77.组合 ">LeetCode-77.组合
- LeetCode-78.子集 ">LeetCode-78.子集
- LeetCode-90.子集 II ">LeetCode-90.子集 II
- LeetCode-216.组合总和 III ">LeetCode-216.组合总和 III
- LeetCode-611.有效三角形的个数 ">LeetCode-611.有效三角形的个数
- LeetCode-1014.最佳观光组合">LeetCode-1014.最佳观光组合
- 排列问题
- 分割问题
- 其他问题
- 树型回溯
组合问题模板算法
0.基本问题-全组合
给一个字符串s，返回s的的所有子字符串，比如”abc”，删除s任意位置的字符得到的新字符串都是s的子字符串，结果集中不能有重复字符串。
1.递归+回溯
（1）无重复值模板
- 叶子节点才将当前组合加入全局结果集
将当前组合加入结果集代码在退出递归代码前面，因为数组的n-1位置元素加入组合后在n位置才被处理
// 全组合默认空集合也加入子集public List<List<Integer>> combination(int[] nums){if(nums == null || nums.length==0){return new ArrayList<>();}List<List<Integer>> res = new ArrayList<>();dfsBackTracking(0, nums, res, new ArrayList<>());return res;}/*** 递归+回溯: 组合树，所有叶子节点就是所有的可能组合，所以到叶子节点后才将当前组合加入结果集* @param idx: 考虑输入数组的第idx位元素是否加入当前组合中* @param nums: 输入数组* @param res: 全局结果集* @param current: 当前组合**/public void dfsBackTracking(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){// 到叶子节点后才将当前组合加入结果集if(idx == nums.length){// 一定要把当前组合的copy加入结果集，不能将其引用直接加入，因为这个引用对应的对象后面将被改变res.add(new ArrayList<>(current));return;}// nums idx位置元素 "加入" 当前组合current.add(nums[idx]);dfsBackTracking(idx+1, nums, res, current);current.remove(current.size()-1);// nums idx位置元素 "不加入" 当前组合dfsBackTracking(idx+1, nums, res, current);}
(2) 有重复值模板-去重
先排序
- 有相同元素时, 前面选择了后面必须选择
思路1：
// 全组合默认空集合也加入子集public List<List<Integer>> combination(int[] nums){if(nums == null || nums.length==0){return new ArrayList<>();}// 排序, 把重复值放在一起好跳过Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();dfsBackTracking(0, nums, res, new ArrayList<>());return res;}/*** 递归+回溯: 组合树，所有叶子节点就是所有的可能组合，所以到叶子节点后才将当前组合加入结果集* 有重复元素时, 比如 "1, 1", 无重复的情况是"", "1", "1, 1",* 去, 前面没有选择, 后面可以选择或者不选择* @param idx: 考虑输入数组的第idx位元素是否加入当前组合中* @param nums: 输入数组* @param res: 全局结果集* @param current: 当前组合**/public void dfsBackTracking(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){// 到叶子节点后才将当前组合加入结果集if(idx == nums.length){// 一定要把当前组合的copy加入结果集，不能将其引用直接加入，因为这个引用对应的对象后面将被改变res.add(new ArrayList<>(current));return;}// nums idx位置元素 "加入" 当前组合current.add(nums[idx]);dfsBackTracking(idx+1, nums, res, current);current.remove(current.size()-1);// 有相同元素时, 前面选择了后面必须选择if(idx>0 && nums[idx]==nums[idx-1] && current.size()>0 &¤t.get(current.size()-1)==nums[idx]){return;}// nums idx位置元素 "不加入" 当前组合dfsBackTracking(idx+1, nums, res, current);}
思路2：
// 递归+去重, 排序序列中每个重复序列片段的元素只能使用其还未使用的最左端元素
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
dfs(nums, 0, new ArrayList<>(), res, new boolean[nums.length]);
return res;
}
public void dfs(int[] nums, int idx, List<Integer> current, List<List<Integer>> res, boolean[] visited){
// 组合的树形分析结构, 在叶子节点处加入结果集
if(idx==nums.length){
res.add(new ArrayList<>(current));
return;
}
// 第0个元素、[1, len-1]区间的元素且和前一个元素不相等、[1, len-1]区间的元素且为重复片段没被使用过的最左端元素
if(idx==0 || nums[idx]!=nums[idx-1] || visited[idx-1]){
current.add(nums[idx]);
visited[idx] = true;
dfs(nums, idx+1, current, res, visited);
current.remove(current.size()-1);
visited[idx] = false;
}
dfs(nums, idx+1, current, res, visited);
}
算法分析：
(1) idx 表示考虑输入数组的idx位置是否加入当前结果集
(2) 每个可能组合加入结果集的时机是在遍历到叶子节点时，既 idx == nums.length 时
2.递归+循环+回溯
(1) 无重复值
// 全组合默认空集合也加入子集
public List<List<Integer>> combination(int[] nums){
if(nums == null || nums.length==0){
return new ArrayList<>();
}
// 排序, 把重复值放在一起好跳过
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
dfsIteratorBackTracking(0, nums, res, new ArrayList<>());
return res;
}
/**
*
* @param idx: 考虑得到输入数组nums的 [idx, n-1] 的所有有效组合(考虑去重)
* @param nums: 输入数组
* @param res: 全局结果集
* @param current: 当前组合
*/
public void dfsIteratorBackTracking(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){
// 将有可能组合加入结果集
res.add(new ArrayList<>(current));
for(int i=idx; i<nums.length;i++){
// 一定是add进入 nums[i] 不是nums[idx]
current.add(nums[i]);
// 这里一定是 i+1不是idx+1, 因为i在递增，idx只是循环的起始值
dfsIteratorBackTracking(i+1, nums, res, current);
current.remove(current.size()-1);
}
}
(2) 有重复值-去重
- 先排序
跳过同层重复值, 不跳过同树枝重复值
// 全组合默认空集合也加入子集 public List<List<Integer>> combination(int[] nums){ if(nums == null || nums.length==0){ return new ArrayList<>(); } // 排序, 把重复值放在一起好跳过 Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); dfsIteratorBackTracking(0, nums, res, new ArrayList<>()); return res; } /** * * @param idx: 考虑得到输入数组nums的 [idx, n-1] 的所有有效组合(考虑去重) * @param nums: 输入数组 * @param res: 全局结果集 * @param current: 当前组合 */ public void dfsIteratorBackTracking(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){ // 将有可能组合加入结果集 res.add(new ArrayList<>(current)); for(int i=idx; i<nums.length;i++){ // 跳过同层重复值, 不跳过同树枝重复值 if(i>idx && nums[i]==nums[i-1]){ continue; } // 一定是add进入 nums[i] 不是nums[idx】 current.add(nums[i]); // 这里一定是 i+1不是idx+1, 因为i在递增，idx只是循环的起始值 dfsIteratorBackTracking(i+1, nums, res, current); current.remove(current.size()-1); } }算法分析：
(1) idx 表示考虑得到输入数组的[idx, n-1]区间的所有元素是否加入当前结果集
(2) 每个可能组合加入结果集的时机是在有了就加入
(3) 循环内部的当前组合add操作和递归操作一定是针对 i 不是idx
3.考虑去重
递归+循环：有重复元素时，前面选择了后面必须选择
递归+循环+迭代：对同层去重，同树枝不去重
组合问题分类
1.组合的累积和为特定值或要求组合的长度为特定值
leetcode-39.组合总和
leetcode-40.组合总和 II
leetcode-216.组合总和 III
2.输入数组的每个元素只能使用一次或可使用无数次(默认输入元素只能使用一次)
只能使用一次: leetcode-40.组合总和 II
可使用无数: leetcode-39.组合总和
3.输入数组中有无重复元素
输入数组无重复元素: leetcode-39.组合总和
输入数组可能有重复元素: LeetCode-40.组合总和 II
4.输入的每个部分可能包含多个基本元素
5.解集中是否可包含重复组合(默认解集不能包含重复组合)
6.定义特定规则校验组合
leetcode-22.括号生成
leetcode-611.有效三角形的个数
7.空集是否为子集
组合问题题单
LeetCode-17.电话号码的字母组合
描述：
思路：
递归+回溯
// 设digits长度为n，就是有n个槽位，每个槽位都有对应的可能的几种字符，把所有可能的字符组合输出即可
// 必须每个槽位都放置了字符时才可以输出
public List<String> letterCombinations(String digits) {
if(digits.length()==0){
return new ArrayList<>();
}
Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
List<String> res = new ArrayList<>();
search(digits, res, new StringBuffer(), 0, map);
return res;
}
// 递归
// res结果集, current是当前放置了字符的所有槽位的字符组合
public void search(String digits, List<String> res, StringBuffer current, int idx, Map<Character, String> map){
// 叶子节点, 每个槽位都放置了字符时才可以输出
if(current.length() == digits.length()){
res.add(current.toString());
}
if(idx>=digits.length()){
return;
}
char digit = digits.charAt(idx);
String chars = map.get(digit);
for(int i=0;i<chars.length();i++){
current.append(chars.charAt(i));
search(digits, res, current, idx+1, map);
current.deleteCharAt(current.length()-1);
}
}
不适合用 “递归+循环+回溯”，因为每个按键都需要有一个值，而”递归+循环+回溯”只能表达一个位置可以有或者没有。
LeetCode-22.括号生成
思路：
把每个左括号或右括号看作是一个基本单元
(1)暴力枚举所有组合,要枚举2^(2n)个字符 然后判断是否合法
(2)枚举时剪枝:
- 左括号-右括号数量<0则不合法停止继续枚举
- 左括号-右括号数量为0时只能枚举左括号
枚举完毕后左括号-右括号数量不等于0不合法
public List<String> generateParenthesis(int n) { if(n<=0){ return new ArrayList<>(); } List<String> res = new ArrayList<>(); backTracking(2*n, 0, res, new StringBuffer()); return res; } // bracketCount是左括号-右括号的数量 // n 是还可以枚举的单个括号的数量 public void backTracking(int n, int bracketCount, List<String> res, StringBuffer current){ if(n==0 && bracketCount==0){ res.add(current.toString()); return; } if(bracketCount<0){ return; } if(n<=0){ return; } // 只能枚举左边 if(bracketCount==0){ current.append('('); bracketCount++; backTracking(n-1, bracketCount, res, current); current.deleteCharAt(current.length() - 1); return; } // 枚举左边 current.append('('); bracketCount++; backTracking(n-1, bracketCount, res, current); current.deleteCharAt(current.length() - 1); // 枚举右边 current.append(')'); bracketCount = bracketCount - 2; backTracking(n-1, bracketCount, res, current); current.deleteCharAt(current.length() - 1); }LeetCode-39.组合总和
描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，candidates 中的数字可以无限制重复被选取。所有数字（包括 target）都是正整数，解集不能包含重复的组合。
思路:
（1）递归+回溯
1.同一位置可以重复选取， 比如一直选0位置多次就可以满足条件， 就不能到叶子节点idx == n-1时才将当前组合加入结果集了。
2.因为输入无重复值，将当前组合加入结果集的条件是当前组合的和等于target，所以全局结果集中不会有重复值。
3.如果是没这个条件 “当前组合的和等于target” 才加入，则相当于树型图中，把叶子节点上面的所有中间节点也会加入到结果集中，全局结果集中就会有重复值
4.搜索终止条件 “ target<0 || idx>=candidates.length” 应该放到 “当前组合加入结果集代码” 后面，因为n-1位置元素加入当前组合后，是idx为n时才考虑将当前组合加入全局结果集// 每个元素都大于0, 所以累积和达到target就可以停止向下搜索 // (1)递归+回溯, 排序:当target小于0时就停止向下搜索 public List<List<Integer>> combinationSum(int[] candidates, int target) { // Arrays.sort(candidates); List<List<Integer>> res = new ArrayList<>(); combinationSum(0, candidates, target, res, new ArrayList<>()); return res; } /** * target: 当前目标值, 会一直减小 * res: 全局结果集 * current: 当前组合 * idx:考虑输入数组的idx位置元素是否被选择 */ public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){ if(target==0){ res.add(new ArrayList<>(current)); return; } // 考虑了所有位置元素是否选择后结束搜索 // 放在当前组合加入全局结果集代码后面的原因： // 因为当前位置被选择后, 当前组合是否被加入全局结果集要在下次搜索时判断 if(target<0 || idx>=candidates.length){ return; } // 当前组合选择 idx 位置元素 current.add(candidates[idx]); // 因为可以重复选则, 所以下次选择还是从idx位置开始 combinationSum(idx, candidates, target-candidates[idx], res, current); // 当前组合不选择 idx 位置元素, 不选择了就从 idx+1 开始 current.remove(current.size()-1); combinationSum(idx+1, candidates, target, res, current); }（2）方法2：递归+循环+回溯
// 每个元素都大于0, 所以累积和达到target就可以停止向下搜索 // (1)递归+回溯, 排序:当target小于0时就停止向下搜索 public List<List<Integer>> combinationSum(int[] candidates, int target) { // Arrays.sort(candidates); List<List<Integer>> res = new ArrayList<>(); combinationSum(0, candidates, target, res, new ArrayList<>()); return res; } /** * target: 当前目标值, 会一直减小 * res: 全局结果集 * current: 当前组合 * idx:考虑输入数组的idx位置元素是否被选择 */ public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){ if(target==0){ res.add(new ArrayList<>(current)); return; } // 考虑了所有位置元素是否选择后结束搜索 // 放在当前组合加入全局结果集代码后面的原因： // 因为当前位置被选择后, 当前组合是否被加入全局结果集要在下次搜索时判断 if(target<0 || idx>=candidates.length){ return; } for(int i=idx;i<candidates.length;i++){ current.add(candidates[i]); // 因为可以重复选则, 所以下次选择还是从 i 位置开始 combinationSum(i, candidates, target-candidates[i], res, current); current.remove(current.size()-1); }
延申问题：如果输入中有重复数字，则必须采用 “递归+循环+回溯” ，因为 “递归+循环”此题无法在 叶子节点时才加入，所以会有重复值。
LeetCode-40.组合总和 II
题目描述：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次，所有数字（包括目标数）都是正整数，解集不能包含重复的组合，数组可能有重复元素
思路：
（1）递归+回溯
一定要在叶子节点时将当前节点加入结果集，否则可能会有重复
去重：有重复元素时，前面选择了后面必须也选择
// 需要去重: 排序+ 相同元素时:前面选择了后面一定要选择
// 输入数组每个位置元素只能使用一次
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length==0){
return new ArrayList<>();
}
// 排序: 将相同元素放一块好去重
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
combinationSum2(0, target, candidates, res, new ArrayList<>());
return res;
}
public void combinationSum2(int idx, int target, int[] candidates, List<List<Integer>> res, List<Integer> current) {
// 递归+回溯, 全组合时必须在叶子节点时才将当前组合加入全局结果集, 否则有重复
if(idx == candidates.length && target==0){
res.add(new ArrayList<>(current));
return;
}
if(target<0 || idx>= candidates.length){
return;
}
// 当前组合选择 idx 位置元素
current.add(candidates[idx]);
combinationSum2(idx+1, target-candidates[idx], candidates, res, current);
current.remove(current.size()-1);
// 有重复元素时, 且前面被选择了则后面必须被选择
if(idx>0 && candidates[idx]==candidates[idx-1] && current.size()>0 &¤t.get(current.size()-1)==candidates[idx]){
return;
}
// 当前组合不选择 idx 位置元素
combinationSum2(idx+1, target, candidates, res, current);
}
（2）递归+循环+回溯
// 需要去重: 排序+ 相同元素时:前面选择了后面一定要选择
// 输入数组每个位置元素只能使用一次
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if(candidates == null || candidates.length==0){
return new ArrayList<>();
}
// 排序: 将相同元素放一块好去重
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
combinationSum2(0, target, candidates, res, new ArrayList<>());
return res;
}
// 递归+排序+回溯
public void combinationSum2(int idx, int target, int[] candidates, List<List<Integer>> res, List<Integer> current) {
if(target==0){
res.add(new ArrayList<>(current));
}
if(target<0){
return;
}
for(int i=idx;i<candidates.length;i++){
// 跳过同层, 不跳过同树枝
if(i>idx && candidates[i]==candidates[i-1]){
continue;
}
current.add(candidates[i]);
combinationSum2(i+1, target-candidates[i], candidates, res, current);
current.remove(current.size()-1);
}
}
LeetCode-77.组合
描述：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
思路：组合长度为 k, 也就是current.size()为 k时将当前组合加入结果集
（1）递归 + 回溯
// 组合长度为 k, 也就是current.size()为 k时将当前组合加入结果集
// 输入是1到n, 所以没有重复数
public List<List<Integer>> combine(int n, int k) {
if(n<k || n<1 || k<1){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
combine(1, n, k, res, new ArrayList<>());
return res;
}
/**
* 递归 + 回溯
* res是结果集
* current是当前组合
* num是当前要考虑是否加入当前组合的数字
* k是输入的k
*/
public void combine(int num, int n, int k, List<List<Integer>> res, List<Integer> current){
// 叶子节点时才将当前组合加入全局结果集
if(num==n+1 && current.size()==k){
res.add(new ArrayList<>(current));
return;
}
if(num>n){
return;
}
// num 加入当前组合
current.add(num);
combine(num+1, n, k, res, current);
current.remove(current.size()-1);
// num 不加入当前组合
combine(num+1, n, k, res, current);
}
（2）递归 +循环+回溯
// 组合长度为 k, 也就是current.size()为 k时将当前组合加入结果集
// 输入是1到n, 所以没有重复数
public List<List<Integer>> combine(int n, int k) {
if(n<k || n<1 || k<1){
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
combine(1, n, k, res, new ArrayList<>());
return res;
}
/**
* 递归 + 循环 + 回溯
* res是结果集
* current是当前组合
* num是当前要考虑是否加入当前组合的数字
* k是输入的k
*/
public void combine(int num, int n, int k, List<List<Integer>> res, List<Integer> current){
if(current.size()==k){
res.add(new ArrayList<>(current));
return;
}
if(num>n){
return;
}
for(int i=num;i<=n;i++){
current.add(i);
combine(i+1, n, k, res, current);
current.remove(current.size()-1);
}
}
LeetCode-78.子集
描述：给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路
（1）递归+回溯
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
subsets(nums, 0, res, new ArrayList<>());
return res;
}
// 递归 + 回溯
public void subsets(int[] nums, int idx, List<List<Integer>> res, List<Integer> currrent) {
// 叶子节点才
if(idx == nums.length){
res.add(new ArrayList<>(currrent));
return;
}
// idx位置元素 加入当前组合
currrent.add(nums[idx]);
subsets(nums, idx+1, res, currrent);
currrent.remove(currrent.size()-1);
// idx位置元素 不加入当前组合
subsets(nums, idx+1, res, currrent);
}
（2）递归+循环+回溯
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
subsets(nums, 0, res, new ArrayList<>());
return res;
}
// 递归 + 循环 + 回溯
public void subsets(int[] nums, int idx, List<List<Integer>> res, List<Integer> currrent) {
res.add(new ArrayList<>(currrent));
for(int i=idx;i<nums.length;i++){
currrent.add(nums[i]);
subsets(nums, i+1, res, currrent);
currrent.remove(currrent.size()-1);
}
}
LeetCode-90.子集 II
描述：给你一个可能包含重复元素的整数数组 nums ，返回该数组所有可能的子集（幂集），解集不能包含重复的子集。返回的解集中的子集可以按 任意顺序 排列。
思路：
（1）递归+回溯
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums == null || nums.length==0){
return new ArrayList<>();
}
// 排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
subsetsWithDup(0, nums, res, new ArrayList<>());
return res;
}
// 递归 + 循环 + 回溯
public void subsetsWithDup(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){
// 叶子节点才将当前组合加入结果集
if(idx==nums.length){
// 将有可能组合加入结果集
res.add(new ArrayList<>(current));
return;
}
// idx位置元素 加入当前结果集
current.add(nums[idx]);
subsetsWithDup(idx+1, nums, res, current);
current.remove(current.size()-1);
// 有重复元素, 而且前面的重复元素选择了,则后面必须选择
if(idx>0 && nums[idx]==nums[idx-1] && current.size()>0 && current.get(current.size()-1)==nums[idx]){
return;
}
// idx位置元素 不加入当前结果集
subsetsWithDup(idx+1, nums, res, current);
}
（2）递归+循环+回溯
public List<List<Integer>> subsetsWithDup(int[] nums) {
if(nums == null || nums.length==0){
return new ArrayList<>();
}
// 排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
subsetsWithDup(0, nums, res, new ArrayList<>());
return res;
}
// 递归 + 循环 + 回溯
public void subsetsWithDup(int idx, int[] nums, List<List<Integer>> res, List<Integer> current){
// 将有可能组合加入结果集
res.add(new ArrayList<>(current));
for(int i=idx; i<nums.length;i++){
// 跳过同层重复值, 不跳过同树枝重复值
if(i>idx && nums[i]==nums[i-1]){
continue;
}
current.add(nums[i]);
// 这里一定是 i+1, 因为i在递增，idx只是循环的起始值
subsetsWithDup(i+1, nums, res, current);
current.remove(current.size()-1);
}
}
LeetCode-216.组合总和 III
思路：输入无重复值, 当前组合的长度为k且所有元素之和为n将current加入res
（1）递归+回溯
// 输入无重复值, 当前组合的长度为k且所有元素之和为n将current加入res
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
combinationSum3(1, k, n, res, new ArrayList<>(), 0);
return res;
}
// 递归 + 回溯
public void combinationSum3(int num, int k, int n, List<List<Integer>> res, List<Integer> current){
// num==10 叶子节点
if(num == 10 && current.size()==k && n==0){
res.add(new ArrayList<>(current));
return;
}
if(num ==10 || current.size()>k || n<0){
return;
}
// num 加入当前组合
current.add(num);
combinationSum3(num+1, k, n-num, res, current);
current.remove(current.size()-1);
// num 不加入当前组合
combinationSum3(num+1, k, n, res, current);
}
（2）递归+循环+回溯
// 输入无重复值, 当前组合的长度为k且所有元素之和为n将current加入res
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
combinationSum3(1, k, n, res, new ArrayList<>());
return res;
}
// 递归 + 循环 + 回溯
public void combinationSum3(int num, int k, int n, List<List<Integer>> res, List<Integer> current){
if(current.size()==k && n==0){
res.add(new ArrayList<>(current));
return;
}
for(int i=num;i<=9;i++){
current.add(i);
combinationSum3(i+1, k, n-i, res, current);
current.remove(current.size()-1);
}
}
LeetCode-611.有效三角形的个数
描述：
思路：
（1）暴力枚举/回溯，
三重循环枚举所有可能组合
（2）二分，
将输入数组排序后，当0
// 结果集可以有重复组合
// 二分:O(N*NlogN)
public int triangleNumber(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
// 排序
Arrays.sort(nums);
int count = 0;
int n = nums.length;
for(int i=0;i<n-2;i++){
for(int j=i+1;j<n-1;j++){
int low = j+1, high = n-1;
// 寻找最大的c,使得a+b>c, high位置就是最大的c
while(low<=high){
int mid = (high-low)/2 + low;
if(nums[mid]>=nums[i]+nums[j]){
high = mid -1;
}else{
low = mid+1;
}
}
// 位置是否溢出, 值是否合法
if(high>j && high<n && nums[high]<nums[i]+nums[j]){
count += high - j;
}
}
}
return count;
}
（3）双指针，
思路：先排序，然后固定最长的那条边，双指针寻找较短的两条边，三条边记作l、r、i，如果nums[l]+nums[r]>nums[i]，那么结果增加r-l个，因为(l,r)、(l+1, r)、(l+2, r)…..(r-1, r)都符合条件
// 双指针, 枚举最长的边, 其余两条边双指针, 时间O(N*N)
public int triangleNumber(int[] nums) {
if(nums==null || nums.length<3){
return 0;
}
// 排序
Arrays.sort(nums);
int res = 0;
// 枚举最长的边
for(int i=nums.length-1;i>=2;i--){
int high = i-1, low = 0;
// 排序后的a<=b<=c,肯定满足a<b+c, b<a+c,只要满足c<a+b, 就可以构成三角形
while(low<high){
if(nums[low]+nums[high]>nums[i]){
res += high - low;
high--;
}else{
low++;
}
}
}
return res;
}
参考:https://leetcode-cn.com/problems/valid-triangle-number/solution/ming-que-tiao-jian-jin-xing-qiu-jie-by-jerring/
LeetCode-1014.最佳观光组合
描述：给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i，一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离，返回一对观光景点能取得的最高分。
思路：O(N)
暴力迭代的优化，观察公式 values[i] + values[j] + i - j = (value[i] +i ) + (values[j] -j)
对每个i求[0, i-1]得 value[i]+i的最大值
设对景点i的最高组合得分为[0, i-1]中任意一个景点和 i的组合最高得分
// values[i] + values[j] + i - j = (value[i] +i ) + (values[j] -j)
// 设对景点i的最高组合得分为[0, i-1]中任意一个景点和 i的组合最高得分
// 统计[0, i-1]的value[i]+i的最大值就可以得到景点i的最高组合得分
public int maxScoreSightseeingPair(int[] values) {
// valueMax是[0, i-1]之前的value[i]+i的最大值
int valueMax = values[0]+0;
// 最高分
int maxScore = 0;
for(int i=1;i<values.length;i++){
maxScore = Math.max(maxScore, values[i]-i + valueMax);
valueMax = Math.max(valueMax, values[i]+i);
}
return maxScore;
}
排列问题
全排列和全组合问题的区别
- 全排列只能使用 “递归 + 循环 + 回溯 +状态表”
- 全组合去重
- “递归+回溯” 重复元素前面被选中，后面一定被选中；
- “递归+循环+回溯” 跳过同层重复值，不跳过同树枝重复
- 递归函数 idx 参数含义：
- 全组合 “递归+回溯” 递归函数 idx表示考虑输入第idx位置是否加入
- 全组合 “递归+循环+回溯” 递归函数 idx表示考虑输入[idx, n-1] 区间构成的组合加入当前组合
- 全排列递归函数无idx参数
全排列去重: 对结果集的每个位置，每次填入的数一定是这个数所在重复数集合中 从左往右第一个未被填过的数字
LeetCode-31.下一个排列
思路：把右边较大的数和左边较小的数交换，较大和较小的数都尽量靠近右边
- 从右向左遍历，查找第一个顺序对，记较小位置为x
- 搜索[x+1, n-1]中第一个大于nums[x]的位置记位y
- 交换x和y位置的值，逆序[x+1, n-1]的值(双指针交换即可，因为[x+1, n-1]有序)
LeetCode-46.全排列
// 递归 + 循环 + 回溯 + 状态 public List<List<Integer>> permute(int[] nums) { if(nums==null || nums.length==0){ return new ArrayList<>(); } List<List<Integer>> res = new ArrayList<>(); permute(nums, res, new ArrayList<>(), new boolean[nums.length]); return res; } public void permute(int[] nums, List<List<Integer>> res, List<Integer> current, boolean[] status){ if(current.size()==nums.length){ res.add(new ArrayList<>(current)); return; } for(int i=0;i<nums.length;i++){ if(status[i]){ continue; } current.add(nums[i]); status[i] = true; permute(nums, res, current, status); current.remove(current.size()-1); status[i] = false; } }LeetCode-47.全排列 II
// 递归 + 循环 + 回溯 + 状态 // 去重: 排序 + 对"结果集的每个位置"来说重复值序列只能选择"从左到右还未被选择的第一个元素" public List<List<Integer>> permuteUnique(int[] nums) { if(nums==null || nums.length==0){ return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); permute(nums, res, new ArrayList<>(), new boolean[nums.length]); return res; } public void permute(int[] nums, List<List<Integer>> res, List<Integer> current, boolean[] status){ if(current.size()==nums.length){ res.add(new ArrayList<>(current)); return; } for(int i=0;i<nums.length;i++){ // 从左往右第一个未被填过的数字 if(status[i] || (i>0 && nums[i]==nums[i-1] && !status[i-1])){ continue; } current.add(nums[i]); status[i] = true; permute(nums, res, current, status); current.remove(current.size()-1); status[i] = false; } }LeetCode-526.优美的排列
思路： 全排列 + 剪枝private int count = 0; // 全排列+剪枝 public int countArrangement(int n) { countArrangement(n, 1, new boolean[n+1]); return count; } // idx表示考虑结果集的idx位置的元素 public void countArrangement(int n, int idx, boolean[] visited){ if(idx==n+1){ count++; return; } for(int i=1;i<=n;i++){ if(visited[i]){ continue; } if(i%idx==0 || idx%i==0){ visited[i] = true; countArrangement(n, idx+1, visited); visited[i] = false; } } }LeetCode-667.优美的排列 II
LeetCode-784.字母大小写全排列
LeetCode-1053.交换一次的先前排列
分割问题
LeetCode-93.复原 IP 地址
LeetCode-131.分割回文串
LeetCode-306.累加数
其他问题
LeetCode-79.单词搜索
LeetCode-89.格雷编码
LeetCode-357.计算各个位数不同的数字个数
LeetCode-797.所有可能的路径
LeetCode-842.将数组拆分成斐波那契序列
LeetCode-967.连续差相同的数字
树型回溯
LeetCode-95.不同的二叉搜索树 II-中等
描述：给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。// 回溯建造二叉搜索树, 对于序列[1..n],假设根节点为i, 则左子树为[1, i-1], 右子树为[i+1, n] // 对左、右子树继续回溯建造二叉搜索树 public List<TreeNode> generateTrees(int n) { if(n==0){ return new ArrayList<>(); } return generateTrees(1, n); } public List<TreeNode> generateTrees(int start, int end){ List<TreeNode> res = new ArrayList<>(); if(start>end){ res.add(null); return res; } if(start==end){ res.add(new TreeNode(start)); return res; } for(int i=start;i<=end;i++){ List<TreeNode> leftChilds = generateTrees(start, i-1); List<TreeNode> rightChilds = generateTrees(i+1, end); for(TreeNode left: leftChilds){ for(TreeNode right: rightChilds){ TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; }
若有收获，就点个赞吧
0 人点赞
